C. Сделай хорошим
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будем называть массив $$$a_1, a_2, \dots, a_m$$$ неотрицательных целых чисел хорошим, если $$$a_1 + a_2 + \dots + a_m = 2\cdot(a_1 \oplus a_2 \oplus \dots \oplus 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}$$$) — элементы, которые вы хотите добавить.

Если существует несколько возможных решений, вы можете вывести любое из них.

Пример
Входные данные
3
4
1 2 3 6
1
8
2
1 1
Выходные данные
0

2
4 4
3
2 6 2
Примечание

В первом тестовом случае из примера, сумма элементов массива равна $$$12$$$, а их $$$\oplus$$$ равен $$$6$$$, поэтому условие уже выполнено.

Во втором тестовом случае из примера, после добавления $$$4, 4$$$, массив принимает вид $$$[8, 4, 4]$$$. Сумма элементов в нем равна $$$16$$$, а их $$$\oplus$$$ равен $$$8$$$.