Make Good
Contest: Good Bye 2019
Difficulty rating: 1400
Tags: bitmasks, constructive algorithms, math

Let's call an array $$$a_1, a_2, \dots, a_m$$$ of nonnegative integer numbers good if $$$a_1 + a_2 + \dots + a_m = 2\cdot(a_1 \oplus a_2 \oplus \dots \oplus a_m)$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

For example, array $$$[1, 2, 3, 6]$$$ is good, as $$$1 + 2 + 3 + 6 = 12 = 2\cdot 6 = 2\cdot (1\oplus 2 \oplus 3 \oplus 6)$$$. At the same time, array $$$[1, 2, 1, 3]$$$ isn't good, as $$$1 + 2 + 1 + 3 = 7 \neq 2\cdot 1 = 2\cdot(1\oplus 2 \oplus 1 \oplus 3)$$$.

You are given an array of length $$$n$$$: $$$a_1, a_2, \dots, a_n$$$. Append at most $$$3$$$ elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements!. So, if an array is good already you are allowed to not append elements.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1\le n \le 10^5)$$$ — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output two lines.

In the first line, output a single integer $$$s$$$ ($$$0\le s\le 3$$$) — the number of elements you want to append.

In the second line, output $$$s$$$ integers $$$b_1, \dots, b_s$$$ ($$$0\le b_i \le 10^{18}$$$) — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case of the example, the sum of all numbers is $$$12$$$, and their $$$\oplus$$$ is $$$6$$$, so the condition is already satisfied.

In the second test case of the example, after adding $$$4, 4$$$, the array becomes $$$[8, 4, 4]$$$. The sum of numbers in it is $$$16$$$, $$$\oplus$$$ of numbers in it is $$$8$$$.

Example input:
3
4
1 2 3 6
1
8
2
1 1

Example output:
0

2
4 4
3
2 6 2

Editorial:
Let the sum of numbers be $$$S$$$, and their $$$\oplus$$$ be $$$X$$$.
Solution 1: If $$$S\le 2X$$$ and $$$S$$$ was even, it would be enough to add into the array $$$2$$$ numbers $$$\frac{2X-S}{2}, \frac{2X-S}{2}$$$: $$$X$$$ wouldn't change, and the sum would become $$$2X$$$.
How to achieve this? Let's add to the array number $$$2^{50} + (S\bmod 2)$$$. If new sum and $$$\oplus$$$ of all numbers are $$$S_1$$$ and $$$X_1$$$ correspondently, then we know, that $$$S_1\le 2\cdot 2^{50} \le 2X_1$$$, and $$$S_1$$$ is even. We spent $$$3$$$ numbers.
Solution 2: It's enough to add to the array numbers $$$X$$$ and $$$S + X$$$. Indeed, $$$S + X + (S+X) = 2(S+X)$$$, and $$$X\oplus X \oplus (S+X) = (S+X)$$$. We spent only $$$2$$$ numbers!
Both solutions have asymptotic $$$O(n)$$$ — to calculate $$$S$$$ and $$$X$$$.
Challenge: What is the smallest possible number of integers that we can add to the given array to make it good?