凯文在月光河公园的河里发现了一个以1开头的二进制字符串$$$s$$$并将其交给了你。你的任务是选择$$$s$$$中的两个非空子串$$$^{\text{*}}$$$(可以重叠),使这两个子串的异或值最大化。
两个二进制字符串 $$$a$$$ 和 $$$b$$$ 的 XOR 被定义为对通过将 $$$a$$$ 和 $$$b$$$ 解释为二进制数而获得的两个数字进行 $$$\oplus$$$ 运算的结果,最左边的位代表最高值。这里,$$$\oplus$$$表示按位异或运算。
您选择的字符串可能有前导零。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。
每个测试用例的唯一行包含一个以 1 开头的二进制字符串 $$$s$$$ ($$$1\le\lvert s\rvert\le 5000$$$)。
保证所有测试用例的 $$$\lvert s\rvert$$$ 总和不超过 $$$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} \l点 s_{r_1}$$$ 和 $$$s_{l_2} s_{l_2 + 1} \l点 s_{r_2}$$$。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
5 111 1000 10111 11101 1100010001101
输出 #1
2 2 1 3 1 3 1 4 1 5 1 4 3 4 1 5 1 13 1 11
注意
在第一个测试用例中,我们可以选择 $$$ 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} $$$,这是最大值。