Background

$\texttt{id: 4d7e}$

Xiao H learned about the XOR operation in class.

For two non-negative integers $x$ and $y$, their XOR is the result obtained by performing the following operation on each bit of their binary representations:

• If the bits of $x$ and $y$ are different, the result bit is $1$;
• If the bits of $x$ and $y$ are the same, the result bit is $0$.

The XOR of $x$ and $y$ is denoted as $x \operatorname{xor} y$ or $x \oplus y$.

In C++, you can use x ^ y to get the XOR value of $x$ and $y$.

Additionally, the XOR of several numbers is called the XOR sum.

Problem Description

Xiao H also learned that the XOR product of a sequence $a$ of length $n$ is a sequence $b$ of the same length, where $b_i$ is equal to the XOR sum of all elements in sequence $a$ except $a_i$, i.e.,

$$b_i = \bigoplus \limits_{j = 1}^{n} [j \ne i] a_j$$

For example, the XOR product of the sequence $\{1, 2, 3, 4\}$ is $\{5, 6, 7, 0\}$.

The XOR product transformation is the process of replacing a sequence with its XOR product. Since the length of the sequence remains unchanged after the XOR product transformation, it can be performed multiple times consecutively.

Now, Xiao H has a sequence $a$ of length $n$, and he wants you to help him calculate the sequence obtained after $k$ XOR product transformations.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

For each test case:

Output one line containing $n$ integers, representing the sequence $a$ after $k$ XOR product transformations.

Sample Input and Output

Sample Input #1

1
4 1
1 2 3 4

Sample Output #1

5 6 7 0

Sample Input #2

1
4 2
0 0 0 1

Sample Output #2

0 0 0 1

Sample Input #3

See the attached file samples/xor3.in

Sample Output #3

See the attached file samples/xor3.ans

Notes

Sample 1 Explanation

This example is the same as the one in the problem description.

Sample 2 Explanation

First XOR product transformation: $\{0,0,0,1\} \to \{1,1,1,0\}$;

Second XOR product transformation: $\{1,1,1,0\} \to \{0,0,0,1\}$.

Data Constraints

For $100\%$ of the test data, $1 \le T \le 10$, $2 \le n \le 10^5$, $1 \le k \le 10^{18}$, $0 \le a_i < 2^{32}$.

Hints

In C++, for data range $0 \le x < 2^{32}$, you can:

• Use unsigned int x to define it;
• Use cin >> x or scanf("%u", &x) to input it;
• Use cout << x or printf("%u", x) to output it.

见题面 Input 部分

见题面 Output 部分