Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is really interested in the XOR operation. He wants to take a sequence $A_{0}, A_{1}, \ldots, A_{N-1}$ and for each $i$ from $0$ to $K-1$ inclusive (in this order, one by one), perform the following operation:
Let's denote $a = A_{i\%N}$ and $b = A_{N-(i\%N)-1}$ before this operation.
Change $A_{i\%N}$ to $a \oplus b$, i.e. $a$ XOR $b$.

Since Chef is busy, he asked you to find the final sequence he should get after performing these operations.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{0}, A_{1}, \ldots, A_{N-1}$.

------ Output ------
For each test case, print a single line containing $N$ space-separated integers ― the elements of the final sequence.

------ Constraints ------
$1 ≤ T ≤ 70$
$1 ≤ N ≤ 10^{4}$
$1 ≤ K ≤ 10^{12}$
$1 ≤ A_{i} ≤ 10^{7}$ for each valid $i$

------ Subtasks ------
Subtask #1 (30 points): $1 ≤ K ≤ 10^{6}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
1

2 2

1 2
----- Sample Output 1 ------
3 1

见题面

见题面