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

Главный секрет киноиндустрии заключается в том, что известный фильм «Люси» основан на реальных событиях, а в главных ролях была именно Тётя Люсине. Спойлер: в конце фильма Люси(не) превращается в компьютер. Причём компьютер необычный, в нём есть информация про все секреты вселенной, но в виде бинарной строки. Эту бинарную строку вам и нужно расшифровать самым-самым естественным образом.

Дана бинарная строка $$$s$$$. Необходимо разбить её на произвольное количество непересекающихся подстрок так, чтобы сумма двоичных чисел, образованных этими подстроками, была точной степенью двойки, либо сказать, что это невозможно. Каждый символ $$$s$$$ должен принадлежать ровно одной подстроке из разбиения.

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

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

В единственной строке каждого набора входных данных вводится бинарная строка $$$s$$$ ($$$1 \le |s| \le 10^6$$$).

Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите ответ на задачу следующим образом:

  • Если ответа не существует, выведите $$$-1$$$.
  • Если ответ существует, то сначала выведите число $$$k$$$ — количество подстрок в разбиении. После этого выведите $$$k$$$ непересекающихся подстрок, для $$$i$$$-й подстроки выведите два целых числа $$$l_i, r_i$$$ ($$$1 \le l_i, r_i \le |s|$$$) — описание $$$i$$$-й подстроки.
Если существует несколько возможных разбиений, выведите любое.
Пример
Входные данные
4
00000
01101
0111011001011
000111100111110
Выходные данные
-1

3
1 3
4 4
5 5

8
1 2
3 3
4 4
5 6
7 7
8 10
11 12
13 13

5
1 5
6 7
8 11
12 14
15 15
Примечание

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

Во втором наборе входных данных возможно следующее разбиение:

  • $$$011_2 = 3_{10}$$$,
  • $$$0_2 = 0_{10}$$$,
  • $$$1_2 = 1_{10}$$$,
$$$3 + 0 + 1 = 4$$$, $$$4$$$ является степенью двойки.