Absolute Zero
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, greedy, math

You are given an array $$$a$$$ of $$$n$$$ integers.

In one operation, you will perform the following two-step move:

1. Choose an integer $$$x$$$ ($$$0 \le x \le 10^{9}$$$).
2. Replace each $$$a_i$$$ with $$$|a_i - x|$$$, where $$$|v|$$$ denotes the absolute value of $$$v$$$.

For example, by choosing $$$x = 8$$$, the array $$$[5, 7, 10]$$$ will be changed into $$$[|5-8|, |7-8|, |10-8|] = [3,1,2]$$$.

Construct a sequence of operations to make all elements of $$$a$$$ equal to $$$0$$$ in at most $$$40$$$ operations or determine that it is impossible. You do not need to minimize the number of operations.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

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

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

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

Output format:
For each test case, output a single integer $$$-1$$$ if it is impossible to make all array elements equal to $$$0$$$ in at most $$$40$$$ operations.

Otherwise, output two lines. The first line of output should contain a single integer $$$k$$$ ($$$0 \le k \le 40$$$) — the number of operations. The second line of output should contain $$$k$$$ integers $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i \le 10^{9}$$$) — the sequence of operations, denoting that on the $$$i$$$-th operation, you chose $$$x=x_i$$$.

If there are multiple solutions, output any of them.

You do not need to minimize the number of operations.

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

Note:
In the first test case, we can perform only one operation by choosing $$$x = 5$$$, changing the array from $$$[5]$$$ to $$$[0]$$$.

In the second test case, no operations are needed because all elements of the array are already $$$0$$$.

In the third test case, we can choose $$$x = 6$$$ to change the array from $$$[4, 6, 8]$$$ to $$$[2, 0, 2]$$$, then choose $$$x = 1$$$ to change it to $$$[1, 1, 1]$$$, and finally choose $$$x = 1$$$ again to change the array into $$$[0, 0, 0]$$$.

In the fourth test case, we can make all elements $$$0$$$ by following the operation sequence $$$(60, 40, 20, 10, 30, 25, 5)$$$.

In the fifth test case, it can be shown that it is impossible to make all elements $$$0$$$ in at most $$$40$$$ operations. Therefore, the output is $$$-1$$$.

Example input:
5
1
5
2
0 0
3
4 6 8
4
80 40 20 10
5
1 2 3 4 5

Example output:
1
5
0

3
6 1 1
7
60 40 20 10 30 25 5
-1

Editorial:
Hint 1
If the array contains both odd and even elements, it is impossible to zero the array.
Hint 2
Is there a method to narrow the range of elements after every operation?
Solution
If the array contains both odd and even numbers, it is impossible to zero the array. This is because any operation will maintain the presence of both odd and even elements.
Otherwise, if all elements in the array are either odd or even, it is feasible to zero the array in no more than $$$31$$$ operations.
The operation strategy works by iteratively narrowing the range of all elements. Initially, the range of all elements is between $$$[0, 2^{30}]$$$. Starting from $$$x = 2^{29}$$$, we use each power of $$$2$$$ as $$$x$$$, reducing the exponent by one each time (i.e., $$$2^{29}, 2^{28}, \ldots, 2^{0}$$$). After each operation, the range of all elements is halved, narrowed down to $$$[0, x]$$$. Continuing this process, after $$$30$$$ operations, all elements will become $$$0$$$ or $$$1$$$. If all elements are $$$1$$$ after $$$30$$$ operations, perform one last operation with $$$x = 1$$$ to turn all $$$1$$$s into $$$0$$$s.