홍준이는 FFT를 좋아해

홍준이는 Fast Fourier Transform(FFT)을 좋아해서 자주 씁니다.

FFT는 합성곱을 계산하는 알고리즘입니다. 길이가 $n$이고 0번째 원소부터 $n-1$번째 원소까지 있는 수열 $a$, $b$가 있을 때, FFT는 아래와 같이 정의된 수열 $c$를 빠르게 구해 줍니다.

$c_i = \sum_{j=0}^{i} a_j b_{i-j}$

홍준이는 이 식에서 합을 최댓값으로 바꿔 보았습니다.

$c_i = \max_{0 \le j \le i} a_j b_{i-j}$

계산하기 편하도록 홍준이는 수열 $a$가 $1$부터 $n$까지의 수를 한 번씩 담고, 수열 $b$는 원소가 0 또는 1인 경우만 생각합니다. 곱한 값이 모두 0이면 $c_i$도 0입니다. 수열 $a$와 $b$가 정해졌을 때 수열 $c$를 구하는 프로그램을 작성하세요.

홍준이는 게을러서 수열 $a$와 $b$의 원소를 일일이 알려주는 것조차 귀찮아합니다. 그래서 세 정수 $n$, $d$, $x$만 주고, 아래 의사코드대로 두 수열을 직접 만들기를 바랍니다. %는 나머지를 구하는 연산이고, swap()은 두 값을 교환하는 함수입니다. 의사코드를 따르면 $b$에는 1이 정확히 $d$개 들어갑니다.

//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)]);
    }
}

첫째 줄에 세 정수 $n$, $d$, $x$가 공백을 사이에 두고 주어집니다. ($1 \le d \le n \le 100{,}000$, $0 \le x \le 1{,}000{,}000{,}006$)

수열 $c$의 원소를 0번째부터 $n-1$번째까지 차례대로 공백을 사이에 두고 한 줄에 출력합니다.