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

Вася и Витя играют в игру. Вася загадал два числа $$$a$$$ и $$$b$$$ от $$$1$$$ до $$$n$$$, а Витя пытается их отгадать. Каждый раунд он говорит Васе два числа $$$x$$$ и $$$y$$$ от $$$1$$$ до $$$n$$$. Если и $$$x=a$$$, и $$$y=b$$$, то Витя побеждает. Иначе Вася должен сказать одну из трёх фраз:

1. $$$x$$$ меньше чем $$$a$$$;
2. $$$y$$$ меньше чем $$$b$$$;
3. $$$x$$$ больше чем $$$a$$$ или $$$y$$$ больше чем $$$b$$$.

Вася не может соврать, но если несколько фраз правдивы, он может выбрать любую из них. Например, если Вася загадал числа $$$2$$$ и $$$4$$$, то на запрос $$$(3, 4)$$$ он ответит фразой $$$3$$$, а на запрос $$$(1, 5)$$$ он может ответит фразой $$$1$$$ или фразой $$$3$$$.

Помогите Вите выиграть не более чем за $$$600$$$ раундов.

Сначала нужно считать число $$$n$$$, после чего можно задавать запросы.

Чтобы задать запрос, выведите два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x, y \leq n$$$), затем выполните операцию flush.

После каждого запроса считайте одно целое число $$$ans$$$ ($$$0 \leq ans \leq 3$$$).

Если $$$ans > 0$$$, то это номер фразы, которую сказал Вася.

Если $$$ans = 0$$$, это означает, что вы выиграли, и ваша программа должна завершиться.

Если вы сделаете более $$$600$$$ запросов или сделаете неправильный запрос, вы получите Wrong Answer.

Ваше решение получит вердикт Idleness Limit Exceeded, если вы не будете ничего выводить или забудете сделать операцию flush после вывода запроса.

Чтобы выполнить операцию flush, сразу после вывода запроса и перевода строки нужно сделать:

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

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

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

В первой строке выведите целое число $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — ограничение на числа.

Во второй строке выведите два целых числа $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq n$$$) — числа, которые загадал Вася.

В третьей строке выведите целое число $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — число инструкций для интерактора.

В следующих $$$m$$$ строках выведите по пять целых чисел: $$$x_i$$$, $$$y_i$$$, $$$r^{12}_i$$$, $$$r^{13}_i$$$ и $$$r^{23}_i$$$ ($$$1 \leq x_i, y_i \leq n$$$), где $$$r^{ST}_i$$$ равно либо цифре $$$S$$$, либо цифре $$$T$$$.

При ответе на запрос $$$x\,\, y$$$, интерактор найдёт целое число $$$i$$$ от $$$1$$$ до $$$n$$$ с минимальным значением $$$|x-x_i| + |y-y_i|$$$. Если таких несколько, то выбирается наименьшее $$$i$$$. Затем интерактор отвечает, но если есть две фразы $$$S$$$ и $$$T$$$, которые можно ответить, то выбирается $$$r^{ST}_i$$$.

Например, файл, задающий тест из примера, такой:

5
2 4
2
2 5 1 1 2
4 1 2 3 3