C. Кольца
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Попал Фродо в плен к Саруману. Сорвал он с шеи Фродо мешочек, вытряхнул его содержимое — а там куча разных колец: золотые и серебряные...

— И как мне теперь определить, которое из них Единое?! — взвыл маг.

— А ты бросай их по очереди в Роковую Расселину и следи, когда Мордор падет!

Где-то в параллельном Средиземье, когда Саруман поймал и обыскал Фродо, он обнаружил лишь $$$n$$$ колец. Причем $$$i$$$-е кольцо было либо золотым, либо серебряным. Для удобства Саруман записал бинарную строку $$$s$$$ из $$$n$$$ символов, где $$$i$$$-м символом был 0, если $$$i$$$-е кольцо золотое, и 1, если серебряное.

У Сарумана есть волшебная функция $$$f$$$, которая принимает бинарную строку, а в ответ выдает число, полученное путем перевода строки в двоичное число, а затем перевода двоичного числа в десятичное. Например, $$$f(001010) = 10, f(111) = 7, f(11011101) = 221$$$.

Саруман, однако, считает, что порядок колец играет какую-то важную роль. Он хочет найти $$$2$$$ пары целых чисел $$$(l_1, r_1), (l_2, r_2)$$$, для которых:

  • $$$1 \le l_1 \le n$$$, $$$1 \le r_1 \le n$$$, $$$r_1-l_1+1\ge \lfloor \frac{n}{2} \rfloor$$$
  • $$$1 \le l_2 \le n$$$, $$$1 \le r_2 \le n$$$, $$$r_2-l_2+1\ge \lfloor \frac{n}{2} \rfloor$$$
  • Пары $$$(l_1, r_1)$$$ и $$$(l_2, r_2)$$$ различны. То есть, должно выполняться хотя бы одно из условий $$$l_1 \neq l_2$$$ и $$$r_1 \neq r_2$$$.
  • Пусть $$$t$$$ — подстрока $$$s[l_1:r_1]$$$ строки $$$s$$$, а $$$w$$$ — подстрока $$$s[l_2:r_2]$$$ строки $$$s$$$. Тогда существует неотрицательное целое число $$$k$$$, такое, что $$$f(t) = f(w) \cdot k$$$.

Здесь подстрока $$$s[l:r]$$$ обозначает $$$s_ls_{l+1}\ldots s_{r-1}s_r$$$, а $$$\lfloor x \rfloor$$$ обозначает округление числа вниз до ближайшего целого.

Помогите Саруману решить эту задачу! Гарантируется, что при ограничениях задачи существует хотя бы одно решение.

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

Каждый тест содержит несколько наборов входных данных.

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

В первой строке каждого набора входных данных находится одно целое положительное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — количество колец.

Во второй строке каждого набора входных данных находится непустая бинарная строка длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите в отдельной строке четыре числа $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, $$$r_2$$$, которые обозначают начало первой подстроки, конец первой подстроки, начало второй подстроки и конец второй подстроки соответственно.

Если существует несколько правильных вариантов ответа, вы можете вывести любой.

Пример
Входные данные
7
6
101111
9
111000111
8
10000000
5
11011
6
001111
3
101
30
100000000000000100000000000000
Выходные данные
3 6 1 3
1 9 4 9
5 8 1 4
1 5 3 5
1 6 2 4
1 2 2 3
1 15 16 30
Примечание

В первом наборе входных данных $$$f(t) = f(1111) = 15$$$, $$$f(w) = f(101) = 5$$$.

Во втором наборе входных данных $$$f(t) = f(111000111) = 455$$$, $$$f(w) = f(000111) = 7$$$.

В третьем наборе входных данных $$$f(t) = f(0000) = 0$$$, $$$f(w) = f(1000) = 8$$$.

В четвертом наборе входных данных $$$f(t) = f(11011) = 27$$$, $$$f(w) = f(011) = 3$$$.

В пятом наборе входных данных $$$f(t) = f(001111) = 15$$$, $$$f(w) = f(011) = 3$$$.