如果 $$$a_1 + a_2 + \dots + a_m = 2\cdot(a_1 \oplus a_2 \oplus \dots \oplus a_m)$$$,则我们称非负整数数组 $$$a_1, a_2, \dots, a_m$$$ 为好,其中 $$$\oplus$$$ 表示按位异或运算。
例如,数组 $$$[1, 2, 3, 6]$$$ 很好,因为 $$$1 + 2 + 3 + 6 = 12 = 2\cdot 6 = 2\cdot (1\oplus 2 \oplus 3 \oplus 6)$$$。同时,数组 $$$[1, 2, 1, 3]$$$ 也不好,因为 $$$1 + 2 + 1 + 3 = 7 \neq 2\cdot 1 = 2\cdot(1\oplus 2 \oplus 1 \oplus 3)$$$。
给定一个长度为 $$$n$$$ 的数组:$$$a_1, a_2, \dots, a_n$$$。最多向其附加 $$$3$$$ 元素以使其良好。附加元素不必不同。可以证明,在给定的约束条件下,解总是存在的。如果有不同的解决方案,您可以输出其中任何一个。请注意,您不必最小化添加元素的数量!。所以,如果一个数组已经很好了,你就可以不追加元素。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1\le n \le 10^5)$$$ — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 10^9$$$) — 数组的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出两行。
在第一行中,输出单个整数 $$$s$$$ ($$$0\le s\le 3$$$) — 要附加的元素数量。
在第二行中,输出 $$$s$$$ 整数 $$$b_1, \dots, b_s$$$ ($$$0\le b_i \le 10^{18}$$$) — 要附加到数组的元素。
如果有不同的解决方案,您可以输出其中任何一个。
示例
输入 #1
3 4 1 2 3 6 1 8 2 1 1
输出 #1
0 2 4 4 3 2 6 2
注意
在示例的第一个测试用例中,所有数字的总和为 $$$12$$$,它们的 $$$\oplus$$$ 为 $$$6$$$,因此条件已满足。
在示例的第二个测试用例中,添加 $$$4, 4$$$ 后,数组变为 $$$[8, 4, 4]$$$。其中的数字总和是$$$16$$$,其中的数字$$$\oplus$$$是$$$8$$$。