Красивий рядок#349

Красивий рядок

1 секунда
256 мегабайтів
Складна

Бінарний рядок — це рядок, який містить лише "0" та "1".

Підрядок рядка — це рядок, який можна отримати, видаливши певну кількість символів з початку та/або кінця.

Сакурако вважає бінарний рядок красивим, якщо кількість одиниць щонайменше і це число ділить довжину рядка.

Наприклад, "1001", "011100" та "010100100" є красивими рядками, але рядки "101", "01010" та "1001000" не є красивими.

Сакурако любить красиві рядки, але їй погано вдається їх шукати. Тому вона просить вас допомогти їй знайти будь-який красивий підрядок заданого рядка.

Вхідні дані

Перший рядок містить одне ціле число (3\le n\le 2\cdot 10^5) — довжина рядка.

Другий рядок містить один бінарний рядок — рядок, в якому Сакурако втратила свій красивий рядок.

Гарантовано, що в рядку є принаймні три символи "1".

Можна довести, що відповідь завжди існує.

Вихідні дані

Виведіть два цілі числа та (1 \leq l \leq r \leq n), де підрядок, що починається з і закінчується в , є красивим. Якщо є кілька рішень, виведіть будь-яке.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі підрядок "1010" є красивим, оскільки довжина, яка дорівнює , ділиться на кількість одиниць, яка дорівнює .

У другому прикладі підрядок "11" є красивим, оскільки довжина, яка дорівнює , ділиться на кількість одиниць, яка дорівнює .

Оцінювання

Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n\le 1000.