#include <bits/stdc++.h>
long long int &getNextX(long long int &x) {
  x = (x * 37 + 10007) % 1000000007;
  return x;
}
void init_ab(std::vector<long long int> &a, std::vector<long long int> &b,
             long long int n, long long int d, long long int x) {
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; ++i) {
    a[i] = i + 1;
  }
  for (int i = 0; i < n; ++i) {
    std::swap(a[i], a[getNextX(x) % (i + 1)]);
  }
  for (int i = 0; i < n; ++i) {
    if (i < d)
      b[i] = 1;
    else
      b[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    std::swap(b[i], b[getNextX(x) % (i + 1)]);
  }
}
int main() {
  long long int n, d, x;
  std::cin >> n >> d >> x;
  std::vector<long long int> a, b;
  a.reserve(100001);
  b.reserve(100001);
  init_ab(a, b, n, d, x);
  std::vector<long long int> a_lookup(n);
  for (int i = 0; i < n; ++i) {
    a_lookup[a[i] - 1] = i;
  }
  std::vector<long long int> b_next_one(n, 0);
  int next_one_index = std::numeric_limits<int>::max();
  for (int i = n - 1; i >= 0; --i) {
    b_next_one[i] = next_one_index;
    if (b[i] == 1) next_one_index = i;
  }
  for (int c_i = 0; c_i < n; ++c_i) {
    for (int n_to_check = n; n_to_check > n - 1000 && n_to_check > 0;
         --n_to_check) {
      int n_to_check_loc = a_lookup[n_to_check - 1];
      if (n_to_check_loc > c_i) continue;
      if (b[c_i - n_to_check_loc] == 1) {
        std::cout << n_to_check << "\n";
        goto c_i_done;
      }
    }
    {
      long long int res = 0;
      if (b[0] == 1) res = a[c_i];
      for (int j = 0; j <= c_i; j = b_next_one[j]) {
        if (b[j] == 1) {
          res = std::max(res, a[c_i - j]);
        }
      }
      std::cout << res << "\n";
    }
  c_i_done:;
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
long long int &getNextX(long long int &x) {
  x = (x * 37 + 10007) % 1000000007;
  return x;
}
void init_ab(std::vector<long long int> &a, std::vector<long long int> &b,
             long long int n, long long int d, long long int x) {
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; ++i) {
    a[i] = i + 1;
  }
  for (int i = 0; i < n; ++i) {
    std::swap(a[i], a[getNextX(x) % (i + 1)]);
  }
  for (int i = 0; i < n; ++i) {
    if (i < d)
      b[i] = 1;
    else
      b[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    std::swap(b[i], b[getNextX(x) % (i + 1)]);
  }
}
int main() {
  long long int n, d, x;
  std::cin >> n >> d >> x;
  std::vector<long long int> a, b;
  a.reserve(100001);
  b.reserve(100001);
  init_ab(a, b, n, d, x);
  std::vector<long long int> a_lookup(n);
  for (int i = 0; i < n; ++i) {
    a_lookup[a[i] - 1] = i;
  }
  std::vector<long long int> b_next_one(n, 0);
  int next_one_index = std::numeric_limits<int>::max();
  for (int i = n - 1; i >= 0; --i) {
    b_next_one[i] = next_one_index;
    if (b[i] == 1) next_one_index = i;
  }
  for (int c_i = 0; c_i < n; ++c_i) {
    for (int n_to_check = n; n_to_check > n - 1000 && n_to_check > 0;
         --n_to_check) {
      int n_to_check_loc = a_lookup[n_to_check - 1];
      if (n_to_check_loc > c_i) continue;
      if (b[c_i - n_to_check_loc] == 1) {
        std::cout << n_to_check << "\n";
        goto c_i_done;
      }
    }
    {
      long long int res = 0;
      if (b[0] == 1) res = a[c_i];
      for (int j = 0; j <= c_i; j = b_next_one[j]) {
        if (b[j] == 1) {
          res = std::max(res, a[c_i - j]);
        }
      }
      std::cout << res << "\n";
    }
  c_i_done:;
  }
  return 0;
}

```