注意:集合 $$$\{s_1,s_2,\ldots,s_m\}$$$ 的异或和定义为 $$$s_1 \oplus s_2 \oplus \ldots \oplus s_m$$$,其中 $$$\oplus$$$ 表示按位异或运算。
在几乎赢得 IOI 后,Victor 给自己买了一个 $$$n\times n$$$ 网格,每个单元格中包含整数。 $$$n$$$ 是偶数。第 $$$i$$$ 行和 $$$j$$$ 列的单元格中的整数为 $$$a_{i,j}$$$。
可悲的是,Mihai 从 Victor 那里偷了网格,并告诉他只要一个条件就能归还它:Victor 必须告诉 Mihai 整个网格中所有整数的异或和。
Victor 不记得网格的所有元素,但他记得一些有关它的信息:对于每个单元格,Victor 记住其所有相邻单元格的异或和。
如果两个单元格共享一条边,则它们被视为邻居 — 换句话说,对于某些整数 $$$1 \le i, j, k, l \le n$$$,如果 $$$|i - k|,则 $$$i$$$ 行和 $$$j$$$ 列中的单元格是 $$$k$$$ 行和 $$$l$$$ 列中的单元格的邻居= 1$$$ 且 $$$j = l$$$,或者如果 $$$i = k$$$ 且 $$$|j - l| = 1$$$。
为了恢复他的网格,维克多向你寻求帮助。你能用维克多记得的信息来找到整个网格的异或和吗?
可以证明答案是唯一的。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 1000$$$) — 网格的大小。
接下来是 $$$n$$$ 行,每行包含 $$$n$$$ 整数。这些行中第 $$$i$$$ 中的第 $$$j$$$ 整数表示第 $$$i$$$ 行和第 $$$j$$$ 列中单元格的所有邻居中的整数的异或和。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$,并且在原始网格中 $$$0 \leq a_{i, j} \leq 2^{30} - 1$$$。
黑客格式
要破解解决方案,请使用以下格式:
第一行应包含一个整数 t ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行应包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 1000$$$) — 网格的大小。
然后是 $$$n$$$ 行,每行包含 $$$n$$$ 整数。这些行中第 $$$i$$$ 中的第 $$$j$$$ 整数是 Victor 原始网格中的 $$$a_{i,j}$$$ 。网格中的值应为 $$$[0, 2^{30}-1]$$$ 范围内的整数
所有测试用例的 $$$n$$$ 总和不得超过 $$$1000$$$。
输出
对于每个测试用例,输出一个整数 - 整个网格的异或和。
示例
输入 #1
3 2 1 5 5 1 4 1 14 8 9 3 1 5 9 4 13 11 1 1 15 4 11 4 2 4 1 6 3 7 3 10 15 9 4 2 12 7 15 1
输出 #1
4 9 5
注意
对于第一个测试用例,Victor 原始网格的一种可能性是:
$$$1$$$$$$3$$$$$$2$$$$$$4$$$
对于第二个测试用例,Victor 原始网格的一种可能性是:
$$$3$$$$$$8$$$$$$8$$$$$$5$$$$$$9$$$$$$5$$$$$$5$$$$$$1$$$$$$5$$$$$$5$$$$$$9$$$$$$9$$$$$$8$$$$$$4$$$$$$2$$$$$$9$$$
对于第三个测试用例,Victor 原始网格的一种可能性是:
$$$4$$$$$$3$$$$$$2$$$$$$1$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$8$$$$$$9$$$$$$9$$$$$$1$$$