Дан массив \(a\) из \(n\) чисел, где все элементы, кроме, возможно, одного, равны \(-1\) или \(1\). Оставшийся элемент \(x\) удовлетворяет условию \(-10^9 \le x \le 10^9\).
Найдите все возможные суммы подмассивов массива \(a\), включая пустой подмассив, сумма которого равна \(0\). Другими словами, найдите все такие числа \(x\), что у массива \(a\) есть хотя бы один подмассив (возможно, пустой) с суммой \(x\). Подмассивом называется непрерывный подотрезок массива.
Выведите эти суммы в порядке возрастания. Каждая сумма должна быть выведена только один раз, даже если достигается на нескольких подмассивах.
Выходные данные
Для каждого набора входных данных выведите две строки:
- в первой строке выведите одно целое число — количество различных сумм на подмассивах;
- во второй строке выведите сами суммы в порядке возрастания.
Каждую сумму следует выводить только один раз, даже если она достигается на нескольких подмассивах.
Примечание
Обозначим за \(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]\).