A9506. 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$ .

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$ .

Output $n$ lines, the $i$ -th line should contain an integer $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]$ .