A2. Нулевая сумма (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между версиями заключается в том, что в этой версии массив содержит нули. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Вам дан массив $$$[a_1, a_2, \ldots a_n]$$$, состоящий из чисел $$$-1$$$, $$$0$$$ и $$$1$$$. Требуется предъявить разбиение этого массива на несколько отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$, обладающее следующим свойством:

  • Обозначим за $$$s_i$$$ знакопеременную сумму элементов в $$$i$$$-м отрезке, то есть $$$s_i$$$ = $$$a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$$$. Например знакопеременная сумма на отрезке $$$[2, 4]$$$ в массиве $$$[1, 0, -1, 1, 1]$$$ равна $$$0 - (-1) + 1 = 2$$$.
  • Сумма значений $$$s_i$$$ по всем отрезкам из разбиения должна быть равна нулю.

Обратите внимание, каждое $$$s_i$$$ не обязано равняться 0, условие стоит только на сумму $$$s_i$$$ по всем отрезкам разбиения.

Набор отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ называется разбиением массива $$$a$$$ длины $$$n$$$, если $$$1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$$$, причем для всех $$$i = 1, 2, \ldots k-1$$$ выполняется $$$r_i + 1 = l_{i+1}$$$. Иными словами, каждый элемент массива должен принадлежать ровно одному отрезку.

Требуется предъявить разбиение массива, обладающее описанными свойствами, или сказать, что такого разбиения не существует.

Обратите внимание, минимизировать количество отрезков в разбиении не требуется.

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

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

Первая строка каждого описания содержит единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — длину массива $$$a$$$.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

Для каждого набора входных данных выведите целое число $$$k$$$ — количество отрезков в получившемся разбиении. Если требуемого разбиения не существует, выведите $$$-1$$$.

Далее, если разбиение существует, то в $$$i$$$-й из следующих $$$k$$$ строк выведите два целых числа $$$l_i$$$ и $$$r_i$$$ — границы $$$i$$$-го отрезка. При этом должны выполняться условия:

  • $$$l_i \le r_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$k$$$.
  • $$$l_{i + 1} = r_i + 1$$$ для всех $$$i$$$ от $$$1$$$ до $$$(k - 1)$$$.
  • $$$l_1 = 1, r_k = n$$$.

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

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

В первом наборе входных данных массив можно просто разбить на $$$4$$$ отрезка по одному элементу, равному $$$0$$$. Тогда общая сумма будет равна $$$0 + 0 + 0 + 0 = 0$$$.

Во втором наборе входных данных массив разбивается на $$$4$$$ отрезка. На первом из них знакопеременная сумма будет равна $$$-1$$$, на втором $$$1$$$, на третьем $$$0 - 1 + 0 = -1$$$, на четвёртом $$$1 - 0 = 1$$$. Получаем общую сумму: $$$-1 + 1 -1 + 1 = 0$$$.

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