Главный секрет киноиндустрии заключается в том, что известный фильм «Люси» основан на реальных событиях, а в главных ролях была именно Тётя Люсине. Спойлер: в конце фильма Люси(не) превращается в компьютер. Причём компьютер необычный, в нём есть информация про все секреты вселенной, но в виде бинарной строки. Эту бинарную строку вам и нужно расшифровать самым-самым естественным образом.
Дана бинарная строка \(s\). Необходимо разбить её на произвольное количество непересекающихся подстрок так, чтобы сумма двоичных чисел, образованных этими подстроками, была точной степенью двойки, либо сказать, что это невозможно. Каждый символ \(s\) должен принадлежать ровно одной подстроке из разбиения.
Выходные данные
Для каждого набора входных данных выведите ответ на задачу следующим образом:
- Если ответа не существует, выведите \(-1\).
- Если ответ существует, то сначала выведите число \(k\) — количество подстрок в разбиении. После этого выведите \(k\) непересекающихся подстрок, для \(i\)-й подстроки выведите два целых числа \(l_i, r_i\) (\(1 \le l_i, r_i \le |s|\)) — описание \(i\)-й подстроки.
Если существует несколько возможных разбиений, выведите любое.
Примечание
В первом наборе входных данных невозможно разбить строку так, чтобы получить степень двойки.
Во втором наборе входных данных возможно следующее разбиение:
- \(011_2 = 3_{10}\),
- \(0_2 = 0_{10}\),
- \(1_2 = 1_{10}\),
\(3 + 0 + 1 = 4\),
\(4\) является степенью двойки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|