CF444B.DZY Loves FFT

DZY loves Fast Fourier Transformation, and he enjoys using it.

Fast Fourier Transformation is an algorithm used to calculate convolution. Specifically, if a, b and c are sequences with length n, which are indexed from 0 to n - 1, and

We can calculate c fast using Fast Fourier Transformation.

DZY made a little change on this formula. Now

To make things easier, a is a permutation of integers from 1 to n, and b is a sequence only containing 0 and 1. Given a and b, DZY needs your help to calculate c.

Because he is naughty, DZY provides a special way to get a and b. What you need is only three integers n, d, x. After getting them, use the code below to generate a and b.

//x is 64-bit variable;
function getNextX() {
x = (x * 37 + 10007) % 1000000007;
return x;
}
function initAB() {
for(i = 0; i < n; i = i + 1){
a[i] = i + 1;
}
for(i = 0; i < n; i = i + 1){
swap(a[i], a[getNextX() % (i + 1)]);
}
for(i = 0; i < n; i = i + 1){
if (i < d)
b[i] = 1;
else
b[i] = 0;
}
for(i = 0; i < n; i = i + 1){
swap(b[i], b[getNextX() % (i + 1)]);
}
}

Operation x % y denotes remainder after division x by y. Function swap(x, y) swaps two values x and y.

DZY 热爱快速傅里叶变换（Fast Fourier Transformation），并乐于使用它。

快速傅里叶变换是一种用于计算卷积的算法。具体而言，若 $a$、$b$ 和 $c$ 是长度均为 $n$ 的序列，下标范围为 $0$ 到 $n-1$，且满足：

则我们可利用快速傅里叶变换高效地计算出序列 $c$。

DZY 对该公式做了一点改动。现在定义为：

为简化问题，$a$ 是 $1$ 到 $n$ 这 $n$ 个整数的一个排列，而 $b$ 是一个仅由 $0$ 和 $1$ 构成的序列。给定 $a$ 和 $b$，DZY 需要你帮助他计算出 $c$。

由于他天性顽皮，DZY 提供了一种特殊的生成 $a$ 和 $b$ 的方式。你只需获得三个整数 $n$、$d$、$x$。获取后，使用以下代码生成 $a$ 和 $b$：

// x 是一个 64 位变量；
function getNextX() {
x = (x * 37 + 10007) % 1000000007;
return x;
}
function initAB() {
for(i = 0; i < n; i = i + 1){
a[i] = i + 1;
}
for(i = 0; i < n; i = i + 1){
swap(a[i], a[getNextX() % (i + 1)]);
}
for(i = 0; i < n; i = i + 1){
if (i < d)
b[i] = 1;
else
b[i] = 0;
}
for(i = 0; i < n; i = i + 1){
swap(b[i], b[getNextX() % (i + 1)]);
}
}

运算符 $x \% y$ 表示 $x$ 除以 $y$ 后所得的余数。函数 swap(x, y) 交换两个值 $x$ 和 $y$。

The only line of input contains three space-separated integers n, d, x (1 ≤ d ≤ n ≤ 100000; 0 ≤ x ≤ 1000000006). Because DZY is naughty, x can't be equal to 27777500.

输入仅包含一行，其中为三个以空格分隔的整数 $n$、$d$、$x$（$1 \le d \le n \le 100000$；$0 \le x \le 1000000006$）。由于 DZY 很淘气，$x$ 不能等于 $27777500$。

Output n lines, the i-th line should contain an integer c__i - 1.

输出 n 行，第 i 行应包含一个整数 c__i - 1。

In the first sample, a is [1 3 2], b is [1 0 0], so _c_0 = max(1·1) = 1, _c_1 = max(1·0, 3·1) = 3, _c_2 = max(1·0, 3·0, 2·1) = 2.

In the second sample, a is [2 1 4 5 3], b is [1 1 1 0 1].

In the third sample, a is [5 2 1 4 3], b is [1 1 1 1 0].

在第一个样例中，$a$ 为 $[1\ 3\ 2]$，$b$ 为 $[1\ 0\ 0]$，因此 $c_0 = \max(1\cdot1) = 1$，$c_1 = \max(1\cdot0,\ 3\cdot1) = 3$，$c_2 = \max(1\cdot0,\ 3\cdot0,\ 2\cdot1) = 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]$。