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.

给你一个二进制字符串 $s$。你需要将它分割成任意数量的互不相交的子串，使得这些子串所表示的二进制整数之和为 2 的幂。字符串 $s$ 中的每个字符必须且仅属于其中一个子串。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是测试用例的描述。

每个测试用例包含一个二进制字符串 $s$（$1 \le |s| \le 10^6$）。

保证所有测试用例的 $|s|$ 之和不超过 $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.

对每个测试用例，按如下格式输出问题的答案：

• 如果答案不存在，输出 $-1$。
• 如果答案存在，首先输出一个整数 $k$ —— 答案中子串的个数；然后输出 $k$ 个互不相交的子串；对第 $i$ 个子串，输出两个整数 $l_i, r_i$（$1 \le l_i, r_i \le |s|$）—— 描述第 $i$ 个子串。

若存在多个合法解，可输出其中任意一个。

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.

在第一个测试用例中，无法将字符串分割成若干子串，使得这些子串的和为 2 的幂。

在第二个测试用例中，如下分割是合法的：

• $011_2 = 3_{10}$,
• $0_2 = 0_{10}$,
• $1_2 = 1_{10}$.

$3 + 0 + 1 = 4$，而 $4$ 是 2 的幂。