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

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

Вам дан массив $$$[a_1, a_2, \ldots a_n]$$$, состоящий из чисел $$$-1$$$ и $$$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$$$ или $$$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$$$.

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

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

В первом наборе входных данных массив можно разбить на один отрезок длины $$$4$$$. Сумма на этом отрезке будет равна $$$1 - 1 + 1 - 1 = 0$$$.

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

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