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

Алиса, Витя, Сева и Антон решили перемешать колоду карт. Для этого они позвали $$$n$$$ своих друзей, усадили их по кругу, пронумеровали от $$$1$$$ до $$$n$$$ против часовой стрелки (то есть друзья $$$i$$$ и $$$i+1$$$ являются соседями, друзья $$$1$$$ и $$$n$$$ тоже соседи) и раздали каждому по $$$k$$$ карт, где $$$k$$$ — четно. Соседом слева человека $$$i$$$ является человек $$$i - 1$$$, а соседом справа — человек $$$i + 1$$$ (за исключением людей $$$1$$$ и $$$n$$$, которые являются соответствующими соседями друг друга).

Каждую секунду происходит следующее: если у человека находится $$$x$$$ карт, то он передаёт $$$\lfloor x / 2 \rfloor$$$ карт своему соседу слева и $$$\lceil x / 2 \rceil$$$ карт соседу справа. Передача карт происходит одновременно для всех игроков.

Оказалось, что человек под номером $$$p$$$ не понял, что он должен делать, и каждую секунду отдаёт все свои карты своему соседу справа. Вы знаете общее число друзей $$$n$$$ и начальное количество карт у каждого из них $$$k$$$, но не знаете $$$p$$$. Ваша задача — узнать $$$p$$$, задавая вопросы вида «сколько карт в данный момент находится у участника с номером $$$q$$$?», где $$$q$$$ — некоторый выбранный вами индекс. После каждого из ваших вопросов участники произведут ровно один ход, передав карты своим соседям. Вам нужно угадать искомую позицию, задав не более $$$1000$$$ вопросов.

Для того, чтобы узнать количество карт в текущий момент у человека под номером $$$q$$$ ($$$1 \le q \le n$$$), выведите в отдельной строке «? $$$q$$$». Процесс перемешивания начинается после вашего первого вопроса, таким образом, ответ на первый вопрос всегда в точности равен $$$k$$$.

Когда вы определили человека, который не понял правила, выведите в отдельной строке «! $$$p$$$», где $$$p$$$ — искомая позиция ($$$1 \le p \le n$$$), и после этого ваша программа должна немедленно завершиться.

Вам требуется найти искомого человека, задав не более, чем $$$1000$$$ вопросов.

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

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

Взломы

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

В единственной строке входных данных должны содержаться три числа $$$n$$$, $$$k$$$ и $$$p$$$ ($$$4 \le n \le 10^5$$$, $$$2 \le k \le 10^9$$$, $$$k$$$ четно, $$$1 \le p \le n$$$) — количество людей, количество карт у каждого из них и искомая позиция.