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

<image>

We can calculate c fast using Fast Fourier Transformation.

DZY made a little change on this formula. Now

<image>

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.

Input

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

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

Examples

Input

3 1 1


Output

1
3
2


Input

5 4 2


Output

2
2
4
5
5


Input

5 4 3


Output

5
5
5
5
4

Note

In the first sample, a is [1 3 2], b is [1 0 0], so c0 = max(1·1) = 1, c1 = max(1·0, 3·1) = 3, c2 = 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].
#include <bits/stdc++.h>
using namespace std;
long long n, d, x;
long long a[100002], b[100002], c[100002], q[100002], pos[100002];
long long sb = 0;
long long getNextX() {
  x = (x * 37 + 10007) % 1000000007;
  return x;
}
void initAB() {
  for (long long i = 0; i < n; i = i + 1) {
    a[i] = i + 1;
  }
  for (long long i = 0; i < n; i = i + 1) {
    swap(a[i], a[getNextX() % (i + 1)]);
  }
  for (long long i = 0; i < n; i = i + 1) {
    if (i < d)
      b[i] = 1;
    else
      b[i] = 0;
  }
  for (long long i = 0; i < n; i = i + 1) {
    swap(b[i], b[getNextX() % (i + 1)]);
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> d >> x;
  initAB();
  for (long long i = 0; i < n; i++) {
    if (b[i]) {
      sb++;
      q[sb] = i;
    }
    pos[a[i]] = i;
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = n; j > n - 30LL; j--) {
      if (j < 1) break;
      if (i >= pos[j] && b[i - pos[j]]) {
        c[i] = j;
        break;
      }
    }
    if (c[i] != 0) continue;
    long long v = 0;
    for (long long j = 1; j <= sb; j++) {
      if (q[j] > i) break;
      v = max(v, a[i - q[j]]);
    }
    c[i] = v;
  }
  for (long long i = 0; i < n; i++) {
    cout << c[i] << "\n";
  }
  return 0;
}
