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

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел. Вам разрешено выполнять следующую операцию:

  • Выберите массив $$$b$$$ размером $$$n$$$, такой что выполняются следующие условия:
    • $$$0 \leq b_i \leq a_i$$$ для каждого $$$1 \leq i \leq n$$$
    • Существует индекс $$$1\leq i \lt n$$$, такой что $$$b_1+b_2+\ldots+b_i=b_{i+1}+b_{i+2}+\ldots+b_n$$$. То есть сумма префикса длины $$$i$$$ равна сумме суффикса длины $$$n-i$$$.
  • Затем вычтите $$$b_i$$$ из $$$a_i$$$ для каждого $$$1 \leq i \leq n$$$.

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

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

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

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

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

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

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

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

Для каждого набора входных данных выведите $$$-1$$$, если решения нет.

В противном случае, сначала выведите целое число $$$s$$$ ($$$1 \leq s \leq 17$$$) — минимальное количество операций для изменения всех элементов массива $$$a$$$ на $$$0$$$.

Затем в следующих $$$s$$$ строках выведите по $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n (0 \leq b_i \leq a_i)$$$, обозначающих массив $$$b$$$ для каждой операции.

После выполнения операций все элементы массива $$$a$$$ должны стать $$$0$$$.

Пример
Входные данные
3
3
1 2 3
2
2 5
4
5 3 1 5
Выходные данные
1
1 2 3
-1
2
3 1 1 1
2 2 0 4
Примечание

В первом наборе входных данных мы можем просто выбрать $$$b=a$$$ в нашей операции. Это допустимо, потому что $$$b_1+b_2=b_3$$$.

Во втором наборе входных данных можно доказать, что невозможно сделать все элементы массива $$$a$$$ равными $$$0$$$.