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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел.

За одну операцию вы можете выполнить следующее двухэтапное действие:

  1. Выбрать целое число $$$x$$$ ($$$0 \le x \le 10^{9}$$$).
  2. Заменить каждое $$$a_i$$$ на $$$|a_i - x|$$$, где $$$|v|$$$ обозначает модуль $$$v$$$.

Например, при выборе $$$x = 8$$$ массив $$$[5, 7, 10]$$$ изменится на $$$[|5-8|, |7-8|, |10-8|] = [3,1,2]$$$.

Постройте последовательность операций, чтобы сделать все элементы $$$a$$$ равными $$$0$$$ не более чем за $$$40$$$ операций или определите, что это невозможно. Вам не нужно минимизировать количество операций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$-1$$$, если невозможно сделать все элементы массива равными $$$0$$$ не более чем за $$$40$$$ операций.

В противном случае выведите две строки. Первая строка должна содержать одно целое число $$$k$$$ ($$$0 \le k \le 40$$$) — количество операций. Вторая строка должна содержать $$$k$$$ целых чисел $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i \le 10^{9}$$$) — последовательность операций, обозначающую, что на $$$i$$$-й операции вы выбрали $$$x=x_i$$$.

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

Вам не обязательно минимизировать количество операций.

Пример
Входные данные
5
1
5
2
0 0
3
4 6 8
4
80 40 20 10
5
1 2 3 4 5
Выходные данные
1
5
0

3
6 1 1
7
60 40 20 10 30 25 5
-1
Примечание

В первом наборе входных данных мы можем получить нужный массив за одну операцию, выбрав $$$x = 5$$$ и изменив массив с $$$[5]$$$ на $$$[0]$$$.

Во втором наборе входных данных никаких операций не требуется, поскольку все элементы массива уже равны $$$0$$$.

В третьем наборе входных данных мы можем выбрать $$$x = 6$$$, чтобы изменить массив с $$$[4, 6, 8]$$$ на $$$[2, 0, 2]$$$, затем выбрать $$$x = 1$$$, чтобы изменить его на $$$[1, 1, 1]$$$, и, наконец, снова выбрать $$$x = 1$$$, чтобы изменить массив на $$$[0, 0, 0]$$$.

В четвертом наборе входных данных мы можем сделать все элементы равными $$$0$$$, выполнив последовательность операций $$$(60, 40, 20, 10, 30, 25, 5)$$$.

В пятом наборе входных данных можно показать, что невозможно сделать все элементы равными $$$0$$$ не более чем за $$$40$$$ операций. Поэтому ответом будет $$$-1$$$.