#2891. 异或积

异或积

题目背景

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

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

  • xxyy 的这一位上不同时,结果的这一位为 11
  • xxyy 的这一位上相同时,结果的这一位为 00

xxyy 的异或被记为 xxoryx \operatorname{xor} yxyx \oplus y

在 C++ 中,你可以用 x ^ y 得到 xxyy 的异或值。

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

题目描述

小 H 还了解到,一个长度为 nn 的数列 aa异或积是一个等长的数列 bb,其中 bib_i 等于数列 aa 中除了 aia_i 以外其他元素的异或和,即

bi=j=1n[ji]ajb_i = \bigoplus \limits_{j = 1}^{n} [j\ne i] a_j

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

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

现在,小 H 有一个长度为 nn 的数列 aa,他想请你帮他计算出 aa 经过 kk 次异或积变换之后得到的序列。

输入格式

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

第一行一个整数 TT,表示测试数据组数。

对于每一组测试数据:

第一行两个整数 n,kn,k

第二行 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n

输出格式

对于每一组测试数据:

一行 nn 个整数,表示数列 aa 经过 kk 次异或积变换之后得到的数列。

样例

1
4 1
1 2 3 4
5 6 7 0
1
4 2
0 0 0 1
0 0 0 1

样例 #3 见附件

提示

样例 1 解释

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

样例 2 解释

11 次异或积变换:{0,0,0,1}{1,1,1,0}\{0,0,0,1\}\to\{1,1,1,0\}

22 次异或积变换:{1,1,1,0}{0,0,0,1}\{1,1,1,0\}\to\{0,0,0,1\}

数据范围

对于 100%100\% 的测试数据,1T101 \le T \le 102n1052 \le n \le 10^51k10181 \le k \le 10^{18}0ai<2320 \le a_i < 2^{32}

测试点编号 nn\leq kk \leq 特殊性质
131 \sim 3 100100
454 \sim 5 10001000
676 \sim 7 33 101810^{18}
8108 \sim 10 10510^5 33
111311 \sim 13 101810^{18} aa 中所有数的异或和为 00
141514 \sim 15 nn 为奇数
161716 \sim 17 nn 为偶数
182018 \sim 20

提示

在 C++ 中,对于数据范围 0x<2320\le x<2^{32},你可以:

  • 使用 unsigned int x 来定义;
  • 使用 cin >> xscanf("%u", &x) 来输入;
  • 使用 cout << xprintf("%u", x) 来输出。