题目描述

Kevin 在月光河公园的河里发现了一个二进制字符串 $s$，它以 1 开头，并把它交给了你。你的任务是从 $s$ 中选择两个非空子串（允许重叠），以使得它们之间的异或值最大。

对于两个二进制字符串 $a$ 和 $b$，它们的异或结果是将 $a$ 和 $b$ 看作二进制数后，进行按位异或操作 $\oplus$ 所得到的结果，其中最左边的位即为最高位。

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

输入格式

输入包含多个测试用例。第一行是测试用例的数量 $t$（$1 \le t \le 10^3$）。

接下来的每个测试用例有一行，包含一个以 1 开头的二进制字符串 $s$（$1 \le |s| \le 5000$）。

保证所有测试用例中 $|s|$ 的总长度不超过 $5000$。

输出格式

对于每个测试用例，输出四个整数 $l_1, r_1, l_2, r_2$（$1 \le l_1 \le r_1 \le |s|$, $1 \le l_2 \le r_2 \le |s|$）——表示你选择的两个子串分别是 $s_{l_1} s_{l_1 + 1} \ldots s_{r_1}$ 和 $s_{l_2} s_{l_2 + 1} \ldots s_{r_2}$。

如果存在多种可能的解，输出任意一种即可。

说明/提示

在第一个测试用例中，我们可以选择 $s_2 = \texttt{1}$ 和 $s_1 s_2 s_3 = \texttt{111}$，此时 $\texttt{1} \oplus \texttt{111} = \texttt{110}$。可以证明这是可能得到的最大值。此外，选择 $l_1 = 3$，$r_1 = 3$，$l_2 = 1$，$r_2 = 3$ 也是一个有效的解决方案。

在第二个测试用例中，选择 $s_1 s_2 s_3 = \texttt{100}$ 和 $s_1 s_2 s_3 s_4 = \texttt{1000}$，则异或结果为 $\texttt{100} \oplus \texttt{1000} = \texttt{1100}$，也是最大的结果。

本翻译由 AI 自动生成

样例

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