CF1684H Hard Cut

You 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.

Each 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 $ .

For 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.

In 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.