题目背景

$\texttt{id: 4d7e}$

小 H 在课堂上学习了异或运算。

对于两个非负整数 $x,y$，它们的异或是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：

• $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
• $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。

$x$ 和 $y$ 的异或被记为 $x \operatorname{xor} y$ 或 $x \oplus y$。

在 C++ 中，你可以用 x ^ y 得到 $x$ 与 $y$ 的异或值。

另外，若干个数的异或称之为异或和。

题目描述

小 H 还了解到，一个长度为 $n$ 的数列 $a$ 的异或积是一个等长的数列 $b$，其中 $b_i$ 等于数列 $a$ 中除了 $a_i$ 以外其他元素的异或和，即

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

例如，数列 $\{1, 2, 3, 4\}$ 的异或积为 $\{5, 6, 7, 0\}$。

异或积变换是指将一个数列用它的异或积替换的过程，由于异或积变换之后数列长度不变，所以异或积变换可以连续进行多次。

现在，小 H 有一个长度为 $n$ 的数列 $a$，他想请你帮他计算出 $a$ 经过 $k$ 次异或积变换之后得到的序列。

输入格式

本题单个测试点内有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

对于每一组测试数据：

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

对于每一组测试数据：

一行 $n$ 个整数，表示数列 $a$ 经过 $k$ 次异或积变换之后得到的数列。

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

提示

样例 1 解释

此样例即为题目描述中的例子。

样例 2 解释

第 $1$ 次异或积变换：$\{0,0,0,1\}\to\{1,1,1,0\}$；

第 $2$ 次异或积变换：$\{1,1,1,0\}\to\{0,0,0,1\}$。

数据规模与约定

对于 $100\%$ 的测试数据，$1 \le T \le 10$，$2 \le n \le 10^5$，$1 \le k \le 10^{18}$，$0 \le a_i < 2^{32}$。

测试点编号	$n\leq$	$k \leq$	特殊性质
$1 \sim 3$	$100$
$4 \sim 5$	$1000$
$6 \sim 7$	$3$	$10^{18}$
$8 \sim 10$	$10^5$	$3$
$11 \sim 13$		$10^{18}$	$a$ 中所有数的异或和为 $0$
$14 \sim 15$			$n$ 为奇数
$16 \sim 17$			$n$ 为偶数
$18 \sim 20$

提示

在 C++ 中，对于数据范围 $0\le x<2^{32}$，你可以：

• 使用 unsigned int x 来定义；
• 使用 cin >> x 或 scanf("%u", &x) 来输入；
• 使用 cout << x 或 printf("%u", x) 来输出。