Kevin 和二进制字符串

https://codeforces.com/problemset/problem/2048/C

Kevin 在月光河公园的河里发现了一个以 1 开头的二进制字符串 \(s\)，然后交给了你。你的任务是从 \(s\) 中选择两个非空子串（允许重叠）以最大化它们的异或值（XOR）。

两个二进制字符串 \(a\) 和 \(b\) 的异或（XOR）值定义为：将 \(a\) 和 \(b\) 作为二进制数解释后，应用按位异或操作 \(\oplus\) 得到的结果。这里，\(\oplus\) 表示按位异或运算。

你选择的子串可以包含前导零。

注：一个字符串 \(a\) 是字符串 \(b\) 的子串，当且仅当可以从 \(b\) 中删除若干个（可以为零个或全部）前缀和若干个后缀字符后得到 \(a\)。

输入格式

每个测试用例包含多个测试点。 第一行是一个整数 \(t\)，表示测试用例的个数。（\(1 \le t \le 10^3\)）

接下来的 \(t\) 行，每行包含一个以 1 开头的二进制字符串 \(s\)（\(1 \le |s| \le 5000\)）。

保证所有测试用例中字符串长度之和不超过 \(5000\)。

输出格式

对于每个测试用例，输出四个整数 \(l_1, r_1, l_2, r_2\)，表示你选择的两个子串分别是 \(s_{l_1}s_{l_1+1} \dots s_{r_1}\) 和 \(s_{l_2}s_{l_2+1} \dots s_{r_2}\)。

如果存在多个解，输出任意一个均可。

示例输入

5
111
1000
10111
11101
1100010001101

示例输出

2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11

说明

第一个测试用例中，我们可以选择 \(s_2 = 1\) 和 \(s_1s_2s_3 = 111\)，\(1 \oplus 111 = 110\)。可以证明没有比这更大的异或值了。\(l_1 = 3, r_1 = 3, l_2 = 1, r_2 = 3\) 也是一个合法解。

第二个测试用例中，\(s_1s_2s_3 = 100\)，\(s_1s_2s_3s_4 = 1000\)，那么 \(100 \oplus 1000 = 1100\)，为最大值。