← 返回题目列表

Codeforces · 444/B

B. DZY 喜欢 FFT

中文机器翻译题面 查看原题

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]。