DZY 喜欢快速傅立叶变换,并且他喜欢使用它。
快速傅立叶变换是一种用于计算卷积的算法。具体地,如果a、b和c是长度为n的序列,其索引从0到n-1,并且
$$c_i = \sum_{j=0}^{i} a_j b_{i-j-1}$$
我们可以使用快速傅立叶变换快速计算 c。
DZY 对这个公式做了一点改变。现在
$$c_i = \max_{j=0}^{i} a_j b_{i-j}$$
为了方便起见,a 是从 1 到 n 的整数的排列,b 是仅包含 0 和 1 的序列。给定 a 和 b,DZY 需要您的帮助来计算 c。
因为他很调皮,DZY提供了一种特殊的方式来获取a和b。你需要的只是三个整数n、d、x。获取后,使用下面的代码生成a和b。
运算 x % y 表示 x 除以 y 后的余数。函数 swap(x, y) 交换两个值 x 和 y。
输入
输入的唯一行包含三个空格分隔的整数 n、d、x(1 ≤ d ≤ n ≤ 100000;0 ≤ x ≤ 1000000006)。因为DZY很调皮,所以x不能等于27777500。
输出
输出n行,第i行应包含整数ci - 1。
示例
输入 #1
3 1 1
输出 #1
1 3 2
输入 #2
5 4 2
输出 #2
2 2 4 5 5
输入 #3
5 4 3
输出 #3
5 5 5 5 4
注意
在第一个示例中,a 为 [1 3 2],b 为 [1 0 0],因此 c0 = max(1·1) = 1,c1 = max(1·0, 3·1) = 3,c2 = max(1·0, 3·0, 2·1) = 2。
在第二个示例中,a 为 [2 1 4 5 3],b 为 [1 1 1 0 1]。
在第三个示例中,a 为 [5 2 1 4 3],b 为 [1 1 1 1 0]。