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

Дан массив $$$a$$$ из $$$n$$$ чисел, где все элементы, кроме, возможно, одного, равны $$$-1$$$ или $$$1$$$. Оставшийся элемент $$$x$$$ удовлетворяет условию $$$-10^9 \le x \le 10^9$$$.

Найдите все возможные суммы подмассивов массива $$$a$$$, включая пустой подмассив, сумма которого равна $$$0$$$. Другими словами, найдите все такие числа $$$x$$$, что у массива $$$a$$$ есть хотя бы один подмассив (возможно, пустой) с суммой $$$x$$$. Подмассивом называется непрерывный подотрезок массива.

Выведите эти суммы в порядке возрастания. Каждая сумма должна быть выведена только один раз, даже если достигается на нескольких подмассивах.

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

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

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива;
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$. В массиве $$$a$$$ существует не более одного элемента, не равного ни $$$1$$$, ни $$$-1$$$.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите две строки:

  • в первой строке выведите одно целое число — количество различных сумм на подмассивах;
  • во второй строке выведите сами суммы в порядке возрастания.

Каждую сумму следует выводить только один раз, даже если она достигается на нескольких подмассивах.

Пример
Входные данные
5
5
1 -1 10 1 1
5
-1 -1 -1 -1 -1
2
-1 2
2
7 1
3
1 4 -1
Выходные данные
8
-1 0 1 2 9 10 11 12 
6
-5 -4 -3 -2 -1 0 
4
-1 0 1 2 
4
0 1 7 8 
6
-1 0 1 3 4 5
Примечание

Обозначим за $$$a[i,j]$$$ подмассив массива $$$a$$$ с $$$i$$$-й позиции по $$$j$$$-ю позицию.

В первом наборе входных данных примера из условия:

  • $$$-1$$$ достигается на подмассиве $$$a[2,2]$$$;
  • $$$0$$$ достигается на пустом подмассиве;
  • $$$1$$$ достигается на подмассиве $$$a[4,4]$$$;
  • $$$2$$$ достигается на подмассиве $$$a[4,5]$$$;
  • $$$9$$$ достигается на подмассиве $$$a[2,3]$$$;
  • $$$10$$$ достигается на подмассиве $$$a[1,3]$$$;
  • $$$11$$$ достигается на подмассиве $$$a[3,4]$$$;
  • $$$12$$$ достигается на подмассиве $$$a[3,5]$$$.