H. Hard Cuttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a binary string s. You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of s should be in exactly one substring.InputEach test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^5). Description of the test cases follows.Each test case contains a binary string s (1 \le |s| \le 10^6).It is guaranteed that the sum of |s| over all test cases does not exceed 10^6.OutputFor each test case output the answer to the problem as follows:   If the answer does not exist, output -1.  If the answer exists, firstly output an integer k — the number of substrings in the answer. After that output k non-intersecting substrings, for i-th substring output two integers l_i, r_i (1 \le l_i, r_i \le |s|) — the description of i-th substring. If there are multiple valid solutions, you can output any of them.ExampleInput
4
00000
01101
0111011001011
000111100111110
Output
-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
NoteIn the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2.In the second test case such cut is valid:   011_2 = 3_{10},  0_2 = 0_{10},  1_2 = 1_{10}.  3 + 0 + 1 = 4, 4 is a power of 2.
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 
['constructive algorithms', 'dfs and similar', 'divide and conquer', 'math', '*3400']