给定一个长度为 $N$ 的整数数组 $X = [x_0, x_1, \dots, x_{N-1}]$。

定义 $X$ 的变换 $F_k(X) = [f_{k,0}(X), f_{k,1}(X), \dots, f_{k,N-1}(X)]$ 如下：

• $k$ 是一个满足 $1 \le k \le N$ 的整数。
• $f_{k,i}(X) = \bigoplus_{j=0}^{k-1} x_{(i+j) \pmod N}$，其中 $i$ 是满足 $0 \le i \le N-1$ 的整数，$\oplus$ 表示按位异或运算。

给定两个整数 $T$ 和 $K$。请计算 $F_K^T(X)$ 的值并输出。注意 $F_K^1(X) = F_K(X)$，且对于 $t > 1$，有 $F_K^t(X) = F_K(F_K^{t-1}(X))$。

输入格式

第一行包含三个整数 $N, K, T$ ($1 \le K \le N \le 10^5, 1 \le T \le 10^{18}$)。 第二行包含 $N$ 个非负整数 $x_0, x_1, \dots, x_{N-1}$ ($0 \le x_i \le 10^9$)，其中 $x_i$ 是数组 $X$ 的第 $i$ 个元素（从 0 开始编号）。

输出格式

设 $F_K^T(X) = [a_0, a_1, \dots, a_{N-1}]$。在第一行输出这 $N$ 个整数 $a_0, a_1, \dots, a_{N-1}$。

样例

输入 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