← 返回题目列表

Codeforces · 1270/C

C. 弥补

中文机器翻译题面 查看原题

如果 $$$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$$$。