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

Это простая версия задачи. Отличия от сложной версии состоят в том, что в простой версии $$$t=1$$$ и количество запросов ограничено числом $$$20$$$.

Поликарп играет в компьютерную игру. В этой игре загадан массив, состоящий из нулей и единиц. Поликарп выиграет, если $$$t$$$ раз угадает позицию $$$k$$$-го слева нуля.

Поликарп может сделать не более $$$20$$$ запросов следующего вида:

• ? $$$l$$$ $$$r$$$ — узнать сумму всех элементов на позициях от $$$l$$$ до $$$r$$$ ($$$1 \le l \le r \le n$$$) включительно.

В этой (простой) версии задачи этот параграф не имеет смысла, так как всегда $$$t=1$$$. Чтобы игра была более интересной, каждый угаданный ноль превращается в единицу и игра продолжается на измененном массиве. Более формально, если позиция $$$k$$$-го нуля равнялась $$$x$$$, тогда после того, как Поликарп угадает эту позицию, $$$x$$$-й элемент массива заменится с $$$0$$$ на $$$1$$$. Конечно, эта особенность на что-либо влияет только при $$$t>1$$$.

Помогите Поликарпу выиграть в игру.

Сначала ваша программа должна считать два целых числа $$$n$$$ и $$$t$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$t=1$$$).

Далее следуют $$$t$$$ строк, каждая из которых содержит одно целое число $$$k$$$ ($$$1 \le k \le n$$$). Гарантируется, что в момент запроса в массиве есть хотя бы $$$k$$$ нулей. Для того, чтобы получить следующее значение $$$k$$$, вы должны вывести ответ для текущего значения $$$k$$$.

После этого вы можете сделать не более $$$20$$$ запросов.

Используйте следующий формат, чтобы вывести ответ (это не считается за запрос, то есть не учитывается в ограничении $$$20$$$):

• ! $$$x$$$ — позиция $$$k$$$-го нуля.

Позиции в массиве нумеруются слева направо от $$$1$$$ до $$$n$$$ включительно.

После вывода $$$t$$$ ответов ваша программа должна немедленно завершиться.

В этой задаче интерактор не адаптивный. Это означает, что в рамках одного теста загаданный массив и запросы не меняются.

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

При превышении количества запросов будет выведен вердикт неправильный ответ.

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

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

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

Взломы

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

В первой строке выведите строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), состоящую из нулей и единиц, и целое число $$$t$$$ ($$$t = 1$$$) — загаданный массив и количество запросов, соответственно. В следующих $$$t$$$ строках выведите число $$$k$$$ ($$$1 \le k \le |s|$$$).

Взламываемое решение не будет иметь прямого доступа к загаданному массиву.