시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 1 1 1 100.000%

문제

You are given an integer array of length $N$: $X = [x_0, x_1, \ldots, x_{N-1}]$.

Let us define a transformation of $X$, which is $F_k(X) = \big[f_{k,0}(X), f_{k,1}(X), \ldots, f_{k,N-1}(X)\big]$, as follows:

  • $k$ is an integer between $1$ and $N$, inclusive.
  • $\displaystyle f_{k,i}(X) = \bigoplus_{j=0}^{k-1} x_{(i+j) \bmod N}$, where $i$ is an integer between $0$ and $N-1$, inclusive, and $\oplus$ is bitwise XOR.

You are also given two integers $T$ and $K$. Calculate the value $F_K^T(X)$ and print it. Note that $F_K^1(X) = F_K(X)$ and $F_K^t(X) = F_K\big(F_K^{t-1}(X)\big)$ for $t > 1$.

입력

The first line contains three integers: $N$, $K$, and $T$ ($1 \leq K \leq N \leq 10^{5}$, $1 \leq T \leq 10^{18}$).

The second line contains $N$ non-negative integers $x_0, x_1, \ldots, x_{N-1}$ ($0 \leq x_i \leq 10^9$), where $x_i$ is the $i$-th element of the array $X$, numbered from zero.

출력

Let $F_K^T(X) = [a_0, a_1, \ldots, a_{N-1}]$. Print the $N$ integers $a_0, a_1, \ldots, a_{N-1}$ on the first line.

예제 입력 1

5 3 1
3 0 2 1 2

예제 출력 1

1 3 1 0 1

예제 입력 2

5 3 2
3 0 2 1 2

예제 출력 2

3 2 0 0 3

예제 입력 3

5 3 3
3 0 2 1 2

예제 출력 3

1 2 3 0 2

예제 입력 4

5 3 15
3 0 2 1 2

예제 출력 4

3 0 2 1 2

예제 입력 5

11 5 1000000000000000000
2 2 4 5 9 1 5 7 7 1 8

예제 출력 5

13 4 5 8 1 0 5 10 3 4 8