#include <bits/stdc++.h>
void int64_print(long long n) {
  long long carry = 10;
  if (n == 0) {
    printf("0");
    return;
  }
  char buf[20];
  buf[0] = '\0';
  int i = 0, j;
  while (n > 0) {
    buf[i] = n % carry;
    n = n / carry;
    i += 1;
  }
  i--;
  for (j = i; j >= 0; j--) {
    printf("%c", 48 + buf[j]);
  }
}
void uint64_print(unsigned long long n) {
  unsigned long long carry = 10;
  char buf[20];
  buf[0] = '\0';
  int i = 0, j;
  while (n > 0) {
    buf[i] = n % carry;
    n = n / carry;
    i += 1;
  }
  i--;
  for (j = i; j >= 0; j--) {
    printf("%c", 48 + buf[j]);
  }
}
unsigned long long uint64_read() {
  char* s = (char*)calloc(20, sizeof(char));
  s[0] = '\0';
  scanf("%s", s);
  unsigned long long ret = 0;
  unsigned long long carry = 1;
  int len = strlen(s), i;
  for (i = 0; i < len; i++) {
    ret += carry * (s[len - 1 - i] - 48);
    carry *= 10;
  };
  free(s);
  return ret;
}
long long int64_read() {
  char* s = (char*)calloc(21, sizeof(char));
  s[0] = '\0';
  scanf("%s", s);
  long long ret = 0;
  long long carry = 1;
  int len = strlen(s), i;
  for (i = 0; i < len; i++) {
    ret += carry * (s[len - 1 - i] - 48);
    carry *= 10;
  };
  free(s);
  return ret;
}
long long x;
int a[100001];
int b[100001];
int n, d;
void swap(int* a, int* b) {
  int c;
  c = *a;
  *a = *b;
  *b = c;
  return;
}
long long getNextX() {
  x = (x * 37 + 10007) % 1000000007;
  return x;
}
void initAB() {
  int i;
  for (i = 0; i < n; i = i + 1) {
    a[i] = i + 1;
  }
  for (i = 0; i < n; i = i + 1) {
    swap(&(a[i]), &(a[(int)(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[(int)(getNextX() % (i + 1))]));
  }
}
int main() {
  scanf("%d %d", &n, &d);
  x = int64_read();
  int i, j;
  initAB();
  int max_a[100000];
  int index_a[100001];
  int sum_b[100000];
  int q[100001];
  q[0] = 0;
  sum_b[0] = b[0];
  max_a[0] = a[0];
  int tmp = -1;
  for (i = 0; i < n; i++) {
    index_a[a[i]] = i;
    if (b[i]) q[++q[0]] = i;
    if (i > 0) {
      sum_b[i] = b[i] + sum_b[i - 1];
    }
    if (sum_b[i] == 0) {
      tmp = i;
    }
  }
  for (i = 0; i <= tmp; i++) {
    max_a[i] = (((a[i]) > (max_a[i - 1])) ? (a[i]) : (max_a[i - 1]));
    printf("0\n");
  }
  for (i = tmp + 1; i < n; i++) {
    int c = 0;
    max_a[i] = (((a[i]) > (max_a[i - 1])) ? (a[i]) : (max_a[i - 1]));
    if (sum_b[i] == i + 1) {
      printf("%d\n", max_a[i]);
      continue;
    }
    int s = 0;
    char next = 0;
    for (j = max_a[i]; j >= 1 && s < 100; j--, s++) {
      if (index_a[j] <= i) {
        if (b[i - index_a[j]]) {
          next = 1;
          printf("%d\n", j);
          break;
        }
      }
    }
    if (next) {
      continue;
    }
    for (j = 1; j <= q[0] && q[j] <= i; j++) {
      c = (((c) > (a[i - q[j]])) ? (c) : (a[i - q[j]]));
    }
    printf("%d\n", c);
  }
  return 0;
}

### Prompt

Please formulate 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>
void int64_print(long long n) {
  long long carry = 10;
  if (n == 0) {
    printf("0");
    return;
  }
  char buf[20];
  buf[0] = '\0';
  int i = 0, j;
  while (n > 0) {
    buf[i] = n % carry;
    n = n / carry;
    i += 1;
  }
  i--;
  for (j = i; j >= 0; j--) {
    printf("%c", 48 + buf[j]);
  }
}
void uint64_print(unsigned long long n) {
  unsigned long long carry = 10;
  char buf[20];
  buf[0] = '\0';
  int i = 0, j;
  while (n > 0) {
    buf[i] = n % carry;
    n = n / carry;
    i += 1;
  }
  i--;
  for (j = i; j >= 0; j--) {
    printf("%c", 48 + buf[j]);
  }
}
unsigned long long uint64_read() {
  char* s = (char*)calloc(20, sizeof(char));
  s[0] = '\0';
  scanf("%s", s);
  unsigned long long ret = 0;
  unsigned long long carry = 1;
  int len = strlen(s), i;
  for (i = 0; i < len; i++) {
    ret += carry * (s[len - 1 - i] - 48);
    carry *= 10;
  };
  free(s);
  return ret;
}
long long int64_read() {
  char* s = (char*)calloc(21, sizeof(char));
  s[0] = '\0';
  scanf("%s", s);
  long long ret = 0;
  long long carry = 1;
  int len = strlen(s), i;
  for (i = 0; i < len; i++) {
    ret += carry * (s[len - 1 - i] - 48);
    carry *= 10;
  };
  free(s);
  return ret;
}
long long x;
int a[100001];
int b[100001];
int n, d;
void swap(int* a, int* b) {
  int c;
  c = *a;
  *a = *b;
  *b = c;
  return;
}
long long getNextX() {
  x = (x * 37 + 10007) % 1000000007;
  return x;
}
void initAB() {
  int i;
  for (i = 0; i < n; i = i + 1) {
    a[i] = i + 1;
  }
  for (i = 0; i < n; i = i + 1) {
    swap(&(a[i]), &(a[(int)(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[(int)(getNextX() % (i + 1))]));
  }
}
int main() {
  scanf("%d %d", &n, &d);
  x = int64_read();
  int i, j;
  initAB();
  int max_a[100000];
  int index_a[100001];
  int sum_b[100000];
  int q[100001];
  q[0] = 0;
  sum_b[0] = b[0];
  max_a[0] = a[0];
  int tmp = -1;
  for (i = 0; i < n; i++) {
    index_a[a[i]] = i;
    if (b[i]) q[++q[0]] = i;
    if (i > 0) {
      sum_b[i] = b[i] + sum_b[i - 1];
    }
    if (sum_b[i] == 0) {
      tmp = i;
    }
  }
  for (i = 0; i <= tmp; i++) {
    max_a[i] = (((a[i]) > (max_a[i - 1])) ? (a[i]) : (max_a[i - 1]));
    printf("0\n");
  }
  for (i = tmp + 1; i < n; i++) {
    int c = 0;
    max_a[i] = (((a[i]) > (max_a[i - 1])) ? (a[i]) : (max_a[i - 1]));
    if (sum_b[i] == i + 1) {
      printf("%d\n", max_a[i]);
      continue;
    }
    int s = 0;
    char next = 0;
    for (j = max_a[i]; j >= 1 && s < 100; j--, s++) {
      if (index_a[j] <= i) {
        if (b[i - index_a[j]]) {
          next = 1;
          printf("%d\n", j);
          break;
        }
      }
    }
    if (next) {
      continue;
    }
    for (j = 1; j <= q[0] && q[j] <= i; j++) {
      c = (((c) > (a[i - q[j]])) ? (c) : (a[i - q[j]]));
    }
    printf("%d\n", c);
  }
  return 0;
}

```