← 返回题目列表

Codeforces · 1684/H

H. 硬切

中文机器翻译题面 查看原题

给你一个二进制字符串$$$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}$$$.