Kevin and Binary Strings
Contest: Codeforces Global Round 28
Difficulty rating: 1200
Tags: bitmasks, brute force, greedy, implementation, strings

Kevin discovered a binary string $$$s$$$ that starts with 1 in the river at Moonlit River Park and handed it over to you. Your task is to select two non-empty substrings$$$^{\text{∗}}$$$ of $$$s$$$ (which can be overlapped) to maximize the XOR value of these two substrings.

The XOR of two binary strings $$$a$$$ and $$$b$$$ is defined as the result of the $$$\oplus$$$ operation applied to the two numbers obtained by interpreting $$$a$$$ and $$$b$$$ as binary numbers, with the leftmost bit representing the highest value. Here, $$$\oplus$$$ denotes the bitwise XOR operation.

The strings you choose may have leading zeros.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$).

The only line of each test case contains a binary string $$$s$$$ that starts with 1 ($$$1\le\lvert s\rvert\le 5000$$$).

It is guaranteed that the sum of $$$\lvert s\rvert$$$ over all test cases doesn't exceed $$$5000$$$.

Output format:
For each test case, output four integers $$$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|$$$) — in the case the two substrings you selected are $$$s_{l_1} s_{l_1 + 1} \ldots s_{r_1}$$$ and $$$s_{l_2} s_{l_2 + 1} \ldots s_{r_2}$$$.

If there are multiple solutions, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can choose $$$ s_2=\texttt{1} $$$ and $$$ s_1 s_2 s_3=\texttt{111} $$$, and $$$ \texttt{1}\oplus\texttt{111}=\texttt{110} $$$. It can be proven that it is impossible to obtain a larger result. Additionally, $$$ l_1=3$$$, $$$r_1=3$$$, $$$l_2=1$$$, $$$r_2=3 $$$ is also a valid solution.

In the second test case, $$$ s_1 s_2 s_3=\texttt{100} $$$, $$$ s_1 s_2 s_3 s_4=\texttt{1000} $$$, the result is $$$ \texttt{100}\oplus\texttt{1000}=\texttt{1100} $$$, which is the maximum.

Example input:
5
111
1000
10111
11101
1100010001101

Example output:
2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11

Editorial:
Hint #1: Is there a substring that must always be selected for all strings?
Hint #2: The substring $$$[1,n]$$$ must be selected. Can we determine the length of the other substring?
Hint #3: Pay special attention to the case where the entire string consists of only $$$1$$$s.
To maximize the XOR sum of the two substrings, we aim to maximize the number of binary digits in the XOR result. To achieve this, the substring $$$[1,n]$$$ must always be selected. Suppose the first character of the other substring is $$$1$$$. If it is not $$$1$$$, we can remove all leading zeros.
Next, find the position of the first $$$0$$$ in the string from left to right. We want this position to be flipped to $$$1$$$, while ensuring that the $$$1$$$s earlier in the string are not changed to $$$0$$$s. Therefore, let the position of the first $$$0$$$ be $$$p$$$. The length of the other substring must be $$$n-p+1$$$. By enumerating the starting position of the other substring and calculating the XOR sum of the two substrings linearly, we can take the maximum value. The time complexity of this approach is $$$O(n^2)$$$.
If the entire string consists only of $$$1$$$s, selecting $$$[1,n]$$$ and $$$[1,1]$$$ can be proven to yield the maximum XOR sum among all possible choices.
Interesting fact: This problem can actually be solved in $$$O(n)$$$ time complexity. Specifically, observe that the other substring needs to satisfy the following conditions: its length is $$$n-p+1$$$, and its first character is $$$1$$$. Thus, its starting position must be less than $$$p$$$. This implies that the length of the prefix of $$$1$$$s in the other substring can be chosen from the range $$$[1, p-1]$$$. We aim to flip the first segment of $$$0$$$s in the original string to $$$1$$$s, while ensuring that the $$$1$$$ immediately after this segment of $$$0$$$s remains unchanged. Let the length of the first segment of $$$0$$$s be $$$q$$$. Then, the length of the prefix of $$$1$$$s in the other substring must be $$$\min(p-1, q)$$$, and the starting position can be determined efficiently.
When preparing the contest and selecting problems, we determined that the $$$O(n)$$$ solution would be too difficult for a Problem C. Therefore, the problem was designed with an $$$O(n^2)$$$ data range to make it more accessible.