Good Bye 2019 |
---|
Закончено |
Будем называть массив $$$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$$$.
Название |
---|