28841번 - Секрет Драконьего глаза 스페셜 저지다국어

문제

Недавно Икинг со своей командой на одном из островов нашел очень древний артефакт --- Драконий глаз. Этот артефакт содержит информацию о всех существующих драконах, которая может помочь найти Короля Драконов!

Недолго думая, Икинг начал разбираться с устройством Драконьего глаза. Оказалось, что внутри него содержится плата, которая активирует устройство при введении правильного кода. Однако, понять, какой же код нужно ввести, не так просто. На ободке драконьего глаза Икинг сразу заметил двоичное число $s$ --- вероятно, шифр. После недели чтения документов и старинных манускриптов, наш герой узнал, что кодом к этому шифру является набор из четырех чисел $l_1,ドル $r_1,ドル $l_2,ドル $r_2,ドル где $[l_1, r_1]$ и $[l_2, r_2]$ представляют собой два разных подотрезка шифра $s$. Эти отрезки должны иметь максимально возможную одинаковую длину, а также одинаковую сумму цифр. Таким образом, ключом к шифру $s$ являются четыре числа $l_1,ドル $r_1,ドル $l_2,ドル $r_2,ドル такие, что:

• $l_1 \le r_1,ドル $l_2 \le r_2$;
• $[l_1, r_1]$ и $[l_2, r_2]$ --- различные подотрезки $s,ドル т.е. $l_1 \neq l_2$ или/и $r_1 \neq r_2$;
• $r_1$ - $l_1$ = $r_2$ - $l_2$;
• $\sum\limits_{i = l_1}^{r_1}s[i] = \sum\limits_{j = l_2}^{r_2}s[j]$;
• $r_1$ - $l_1$ максимально.

Насколько Икинг понял из манускрипта, если в качестве кода подходят несколько четверток чисел, ввести можно любую! Теперь Икингу нужно найти код к заветному шифру, но с этим ему не справиться без вашей помощи. Помогите юному викингу.

입력

В единственной строке содержится двоичная строка $s$ --- шифр на ободке Драконьего глаза (1ドル \le |s| \le 10^6$). Гарантируется, что строка состоит только из символов <<0>> и <<1>>.

출력

Если такой четверки чисел не существует, выведите <<-1>> (без кавычек). Иначе, в единственной строке выведите четыре числа $l_1,ドル $r_1,ドル $l_2$ и $r_2$ соответственно --- код шифра к Драконьему глазу. Если существует несколько ответов, выведите любой из них.

제한

노트

В первом примере строки $s[1..5] = "11111"$ и $s[2..6] = "11111"$ имеют одинаковую сумму битов 5ドル,ドル одинаковую длину, а также не совпадают. Так как вся строка имеет длину 6ドル,ドル лучше ответа не существует.

Во втором примере строки $s[2..5] = "1010"$ и $s[3..6] = "0101"$ имеют одинаковую сумму битов 2ドル,ドル одинаковую длину, а также не совпадают. Подстрок большей длины, удовлетворяющих всем условиям, не существует.