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

Задан массив целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$). За одну операцию можно выбрать целое число $$$x$$$ ($$$0 \le x \le 10^{18}$$$) и заменить $$$a_i$$$ на $$$\lfloor \frac{a_i + x}{2} \rfloor$$$ ($$$\lfloor y \rfloor$$$ означает округление $$$y$$$ вниз до ближайшего целого числа) для всех $$$i$$$ от $$$1$$$ до $$$n$$$. Обратите внимание, что каждая операция затрагивает все элементы массива.

Выведите наименьшее количество операций, необходимое, чтобы сделать все элементы массива равными.

Если количество операций меньше или равно $$$n$$$, то выведите выбранный $$$x$$$ для каждой операции. Если есть несколько правильных ответов, то выведите любой из них.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

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

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

На каждый набор входных данных выведите наименьшее количество операций, необходимое, чтобы сделать все элементы массива равными.

Если количество операций меньше или равно $$$n$$$, то выведите выбранный $$$x$$$ для каждой операции. Если есть несколько правильных ответов, то выведите любой из них.

Пример
Входные данные
4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32
Выходные данные
0
2
2 5
1
1
6
Примечание

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

Во втором наборе нельзя сделать меньше $$$2$$$ операций. Ответов несколько, рассмотрим последовательность ответов $$$[2, 5]$$$. После применения операции с $$$x = 2$$$ массив станет равен $$$[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$$$. После применения операции с $$$x = 5$$$ массив станет равен $$$[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$$$. Оба элемента одинаковые, поэтому мы закончили.

В последнем наборе нельзя сделать меньше $$$6$$$ операций. Так как $$$6$$$ больше $$$n$$$, не требуется выводить их. Одна из возможных последовательностей ответов — $$$[0, 0, 0, 0, 0, 0]$$$. Мы просто делим второй элемент на $$$2$$$ каждый раз и не изменяем первый элемент.