Background

$\texttt{id: 4d7e}$

Little H learned about the XOR operation in class.

For two non-negative integers $x, y$, their XOR is defined as follows: treat them as binary numbers, and for each bit position compute the result bit by bit:

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

The XOR of $x$ and $y$ is written 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$.

Also, the XOR of multiple numbers is called the XOR sum.

Problem Description

Little 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$ equals the XOR sum of all elements in $a$ except $a_i$, that is,

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

A XOR product transformation means replacing a sequence with its XOR product. Since the sequence length does not change after a transformation, the XOR product transformation can be applied multiple times in a row.

Now, Little H has a sequence $a$ of length $n$. He wants you to help him compute the sequence obtained after applying $k$ XOR product transformations to $a$.

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, k$.

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

Output Format

For each test case:

Output one line with $n$ integers, representing the sequence obtained after applying $k$ XOR product transformations to sequence $a$.

1
4 1
1 2 3 4

5 6 7 0

1
4 2
0 0 0 1

0 0 0 1

见附件中的 samples/xor3.in

见附件中的 samples/xor3.ans

Hint

Explanation for Sample 1

This sample is exactly the example given in the statement.

Explanation for Sample 2

After the 1st XOR product transformation: $\{0,0,0,1\}\to\{1,1,1,0\}$;

After the 2nd XOR product transformation: $\{1,1,1,0\}\to\{0,0,0,1\}$.

Constraints

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

Notes

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

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

Translated by ChatGPT 5