C. Кевин и бинарные строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин обнаружил бинарную строку $$$s$$$, которая начинается с 1 и передал её вам. Ваша задача — выбрать две непустые подстроки$$$^{\text{∗}}$$$ строки $$$s$$$ (которые могут пересекаться), чтобы максимизировать значение XOR этих двух подстрок.

XOR двух бинарных строк $$$a$$$ и $$$b$$$ определяется как результат операции $$$\oplus$$$, примененной к двум числам, полученным путем представления $$$a$$$ и $$$b$$$ как бинарных чисел, где самый левый бит является старшим. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ (XOR).

Выбранные вами строки могут содержать ведущие нули.

$$$^{\text{∗}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов с начала и нескольких (возможно, ни одного или всех) символов с конца.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов $$$t$$$ ($$$1 \le t \le 10^3$$$).

Единственная строка каждого набора содержит бинарную строку $$$s$$$, которая начинается с 1 ($$$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} \ldots s_{r_1}$$$ и $$$s_{l_2} s_{l_2 + 1} \ldots 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=\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} $$$, что является максимумом.