← 返回题目列表

Codeforces · 1562/C

C. 戒指

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

在平行中土世界的某个地方,当萨鲁曼抓住佛罗多时,他只发现了$$$n$$$戒指。第 $$$i$$$ 戒指要么是金的,要么是银的。为了方便起见,萨鲁曼写下了一个由 $$$n$$$ 个字符组成的二进制字符串 $$$s$$$,其中,如果第 $$$i$$$ 戒指是金戒指,则第 $$$i$$$ 字符为 0,如果是银戒指,则第 $$$i$$$ 字符为 1。

Saruman有一个神奇的函数$$$f$$$,它接受一个二进制字符串,并返回一个数字,该数字是将字符串转换为二进制数,然后将二进制数转换为十进制数。例如,$$$f(001010) = 10、f(111) = 7、f(11011101) = 221$$$。

然而,萨鲁曼认为环的顺序起着重要作用。他想要找到 $$$2$$$ 整数对 $$$(l_1, r_1), (l_2, r_2)$$$,这样:

- $$$1 \le l_1 \le n$$$、$$$1 \le r_1 \le n$$$、$$$r_1-l_1+1\ge \lfloor \frac{n}{2} \rfloor$$$
- $$$1 \le l_2 \le n$$$、$$$1 \le r_2 \le n$$$、$$$r_2-l_2+1\ge \lfloor \frac{n}{2} \rfloor$$$
- 对 $$$(l_1, r_1)$$$ 和 $$$(l_2, r_2)$$$ 是不同的。也就是说,$$$l_1 \neq l_2$$$ 和 $$$r_1 \neq r_2$$$ 中至少一个必须成立。
- 令 $$$t$$$ 为 $$$s$$$ 的子串 $$$s[l_1:r_1]$$$,$$$w$$$ 为 $$$s$$$ 的子串 $$$s[l_2:r_2]$$$。那么存在非负整数$$$k$$$,使得$$$f(t) = f(w) \cdot k$$$。

这里子字符串 $$$s[l:r]$$$ 表示 $$$s_ls_{l+1}\ldots s_{r-1}s_r$$$,$$$\lfloor x \rfloor$$$ 表示将数字向下舍入到最接近的整数。

帮助萨鲁曼解决这个问题!保证在问题的约束下至少存在一个解。

输入

每个测试包含多个测试用例。

第一行包含一个正整数$$$t$$$ ($$$1 \le t \le 10^3$$$),表示测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — 字符串的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的非空二进制字符串。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印四个整数 $$$l_1$$$、$$$r_1$$$、$$$l_2$$$、$$$r_2$$$,分别表示第一个子字符串的开头、第一个子字符串的结尾、第二个子字符串的开头和第二个子字符串的结尾。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

7
6
101111
9
111000111
8
10000000
5
11011
6
001111
3
101
30
100000000000000100000000000000

输出 #1

3 6 1 3
1 9 4 9
5 8 1 4
1 5 3 5
1 6 2 4
1 2 2 3
1 15 16 30

注意

在第一个测试用例中 $$$f(t) = f(1111) = 15$$$, $$$f(w) = f(101) = 5$$$。

在第二个测试用例中,$$$f(t) = f(111000111) = 455$$$,$$$f(w) = f(000111) = 7$$$。

在第三个测试用例中 $$$f(t) = f(0000) = 0$$$, $$$f(w) = f(1000) = 8$$$。

在第四个测试用例中 $$$f(t) = f(11011) = 27$$$, $$$f(w) = f(011) = 3$$$。

在第五个测试用例中,$$$f(t) = f(001111) = 15$$$,$$$f(w) = f(011) = 3$$$。