Попал Фродо в плен к Саруману. Сорвал он с шеи Фродо мешочек, вытряхнул его содержимое — а там куча разных колец: золотые и серебряные...— И как мне теперь определить, которое из них Единое?! — взвыл маг.
— А ты бросай их по очереди в Роковую Расселину и следи, когда Мордор падет!
Где-то в параллельном Средиземье, когда Саруман поймал и обыскал Фродо, он обнаружил лишь \(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\) обозначает округление числа вниз до ближайшего целого.
Помогите Саруману решить эту задачу! Гарантируется, что при ограничениях задачи существует хотя бы одно решение.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке четыре числа \(l_1\), \(r_1\), \(l_2\), \(r_2\), которые обозначают начало первой подстроки, конец первой подстроки, начало второй подстроки и конец второй подстроки соответственно.
Если существует несколько правильных вариантов ответа, вы можете вывести любой.
Примечание
В первом наборе входных данных \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|