Кевин обнаружил бинарную строку \(s\), которая начинается с 1 и передал её вам. Ваша задача — выбрать две непустые подстроки\(^{\text{∗}}\) строки \(s\) (которые могут пересекаться), чтобы максимизировать значение XOR этих двух подстрок.
XOR двух бинарных строк \(a\) и \(b\) определяется как результат операции \(\oplus\), примененной к двум числам, полученным путем представления \(a\) и \(b\) как бинарных чисел, где самый левый бит является старшим. Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ (XOR).
Выбранные вами строки могут содержать ведущие нули.
Выходные данные
Для каждого тестового случая выведите четыре целых числа \(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} \), что является максимумом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|