B. DZY любит БПФ
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

DZY очень любит быстрое преобразование Фурье.

Быстрое преобразование Фурье — это алгоритм, используемый для эффективного подсчета свертки. В частности, если a, b и c — последовательности длины n, элементы которых индексированы от 0 до n - 1, и

Можно эффективно посчитать элементы последовательности c с помощью быстрого преобразования Фурье.

DZY внес небольшое изменение в формулу свертки. Теперь

Чтобы упростить себе задачу, будем считать, что a — перестановка целых чисел от 1 до 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.

Входные данные

В единственной строке записаны три целых числа через пробел n, d, x (1 ≤ d ≤ n ≤ 100000; 0 ≤ x ≤ 1000000006). Как уже было сказано, DZY крайне капризный, поэтому x не может равняться 27777500.

Выходные данные

Выведите n строк, в i-й строке выведите значение ci - 1.

Примеры
Входные данные
3 1 1
Выходные данные
1
3
2
Входные данные
5 4 2
Выходные данные
2
2
4
5
5
Входные данные
5 4 3
Выходные данные
5
5
5
5
4
Примечание

В первом примере a равняется [1 3 2], b равняется [1 0 0], таким образом, c0 = max(1·1) = 1, c1 = max(1·0, 3·1) = 3, c2 = max(1·0, 3·0, 2·1) = 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].