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

Наташа собирается полететь на Марс. Наконец Наташа села в ракету. Летит она, летит. Скучно как-то. Побыстрее бы уже на Марс прилететь! Решила она занять себя чем-то. И ничего интересней она не придумала, как считать, какое расстояние осталось ей преодолеть до красной планеты.

Пусть расстояние до Марса равно $$$x$$$. К сожалению, Наташа не знает $$$x$$$. Зато известно, что $$$1 \le x \le m$$$, где число $$$m$$$ Наташа знает. Кроме того, $$$x$$$ и $$$m$$$ — целые положительные числа.

Наташа может задавать ракете вопросы. Каждый вопрос — это целое число $$$y$$$ ($$$1 \le y \le m$$$). Правильный ответ — это $$$-1$$$, если $$$x<y$$$, $$$0$$$, если $$$x=y$$$ и $$$1$$$, если $$$x>y$$$. Но ракета сломалась — она не всегда отвечает правду. А именно: пусть правильный ответ на текущий вопрос равен $$$t$$$, тогда, если ракета отвечает на этот вопрос правду, то она ответит $$$t$$$, в противном случае — ответит $$$-t$$$.

Кроме того, у ракеты есть последовательность $$$p$$$ длины $$$n$$$. Каждый её элемент — это $$$0$$$ или $$$1$$$. Ракета обрабатывает эту последовательность циклически по порядку, то есть $$$1$$$-й элемент, $$$2$$$-й, $$$3$$$-й, $$$\ldots$$$, $$$(n-1)$$$-й, $$$n$$$-й, $$$1$$$-й, $$$2$$$-й, $$$3$$$-й, $$$\ldots$$$, $$$(n-1)$$$-й, $$$n$$$-й, $$$\ldots$$$. Если текущий элемент равен $$$1$$$, то ракета отвечает правду, если $$$0$$$ — неправду. Наташа не знает последовательность $$$p$$$, но знает её длину — $$$n$$$.

Вы можете задать ракете не более $$$60$$$ вопросов.

Помогите Наташе узнать расстояние до Марса. Считайте, что, пока Наташа задаёт вопросы, расстояние до Марса не меняется.

Ваше решение не будет засчитано, если оно не получит ответ $$$0$$$ от ракеты (даже если расстояние до Марса однозначно определяется уже полученными ответами ракеты).

Вы можете задать ракете не более $$$60$$$ вопросов.

Чтобы задать вопрос, выведите число $$$y$$$ ($$$1\le y\le m$$$) и перевод строки, затем сделайте операцию flush и прочитайте ответ ракеты на вопрос.

Если программа прочитает $$$0$$$, то расстояние правильное и нужно немедленно завершить программу (например, вызовом exit(0)). Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Если в какой-то момент ваша программа считывает $$$-2$$$ как ответ, она должна немедленно завершиться (например, вызовом exit(0)). Вы получите вердикт «Неправильный ответ», и это будет означать, что запрос некорректен или количество запросов превышает $$$60$$$. Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Если запрос вашей программы не будет корректным целым числом между $$$-2^{31}$$$ и $$$2^{31}-1$$$ (включительно) без лидирующих нулей, то вы можете получить любой вердикт.

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

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

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

Взломы

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

В первой строке введите $$$3$$$ целых числа $$$m,n,x$$$ ($$$1\le x\le m\le 10^9$$$, $$$1\le n\le 30$$$) — максимальное расстояние до Марса, количество элементов последовательности $$$p$$$ и текущее расстояние до Марса.

Во второй строке введите $$$n$$$ чисел, каждое из которых равно $$$0$$$ или $$$1$$$ — последовательность $$$p$$$.

У взламываемого решения не будет доступа к числу $$$x$$$ и последовательности $$$p$$$.