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