Это интерактивная задача.

У жюри есть строка $$$s$$$ из строчных латинских букв. На эту строку наложены такие ограничения:

• строка имеет нечетную длину, которая не превышает $$$99$$$;
• строка состоит только из символов «a» и «b».

Также есть строка $$$t$$$, которая изначально пуста. Затем происходит $$$|s|$$$ шагов. На $$$i$$$-м шаге происходят следующие события:

• сначала жюри сообщает вам символ $$$s_i$$$ и дописывает его в конец строки $$$t$$$;
• затем вы можете либо поменять местами любые два символа в $$$t$$$, либо ничего не делать.

Ваша задача — добиться того, чтобы после $$$|s|$$$-го шага строка $$$t$$$ была палиндромом.

Сразу начинается интерактивное взаимодействие.

В рамках каждого шага ваша программа будет получать один символ — следующий символ строки $$$s$$$ или «0» (ноль), если строка закончилась. Если получен символ «0», то ваша программа должна немедленно завершить исполнение.

После получения $$$s_{i}$$$ вы должны вывести позиции переставляемых символов, то есть два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l,r \le i$$$) или, если вы не хотите менять символы, то «0 0».

Если ваша программа выполнит невалидную операцию (например, попытается поменять местами символы на несуществующих позициях), или итоговая строка $$$t$$$ не окажется палиндромом, программа жюри выведет один символ «X» на отдельной строке. Как только ваша программа получит в качестве ответа «X», она должна немедленно завершиться; в противном случае вердикт тестирования вашего решения будет неопределенным.

Интерактор в данной задаче не является адаптивным, то есть строка $$$s$$$ не изменяется в процессе взаимодействия.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт «Решение зависло». Для этого используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• sys.stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Для взломов используйте следующий формат.

Первая строка должна содержать одно целое число $$$|s|$$$ — длина строки $$$s$$$.

Вторая строка должна содержать саму $$$s$$$ ($$$1 \le |s| \le 99, |s| \bmod 2 = 1$$$), состоящую из строчных латинских букв «a» и «b».