给你一个二进制字符串$$$s$$$。你必须将它切割成任意数量的不相交的子串,以便这些子串表示的二进制整数之和是2的幂。$$$s$$$的每个元素都应该恰好在一个子串中。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例都包含一个二进制字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$)。
保证所有测试用例的$$$|s|$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出问题的答案如下:
- 如果答案不存在,则输出$$$-1$$$。
- 如果答案存在,首先输出一个整数$$$k$$$——答案中子串的数量。之后输出 $$$k$$$ 不相交的子串,对于第 $$$i$$$ 个子串,输出两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i, r_i \le |s|$$$) — 第 $$$i$$$ 个子串的描述。
如果有多个有效解,则可以输出其中任何一个。
示例
输入 #1
4 00000 01101 0111011001011 000111100111110
输出 #1
-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
注意
在第一个测试用例中,不可能将字符串切割成子字符串,因此总和是 2 的幂。
在第二个测试用例中,这样的剪切是有效的:
- $$$011_2 = 3_{10}$$$,
- $$$0_2 = 0_{10}$$$,
- $$$1_2 = 1_{10}$$$.