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

Вы нашли на чердаке числа $$$k$$$ и $$$n$$$, но потеряли два массива $$$A$$$ и $$$B$$$.

Вы помните, что:

• $$$|A| + |B| = n$$$, суммарная длина массивов равна $$$n$$$.
• $$$|A| \geq k$$$ и $$$|B| \geq k$$$, длина каждого из массивов как минимум $$$k$$$.
• Массивы состоят только из чисел от $$$1$$$ до $$$k$$$.
• Если взять любые $$$k$$$ подряд идущих элементов из массива $$$A$$$, то они все будут различными. Если взять любые $$$k$$$ подряд идущих элементов из массива $$$B$$$, то они все также будут различными.

К счастью, добрый дух, который поселился на чердаке, нашёл эти массивы и склеил их в массив $$$C$$$ длиной $$$n$$$. То есть сначала в массив $$$C$$$ были по очереди записаны элементы массива $$$A$$$, а затем — элементы массива $$$B$$$.

Вы можете задать доброму духу до $$$250$$$ вопросов. Каждый вопрос содержит индекс $$$i$$$ ($$$1 \leq i \leq n$$$). В ответ вы получите $$$i$$$-й элемент склеенного массива $$$C$$$.

Вам требуется найти длины массивов $$$A$$$ и $$$B$$$, либо сообщить, что это невозможно сделать однозначно.

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Затем вы можете сделать до $$$250$$$ запросов.

Чтобы сделать запрос, выведите строку в формате «? x» (без кавычек) ($$$1 \leq x \leq n$$$). После каждого запроса считайте целое число — ответ на ваш запрос.

Если вы сделаете слишком много запросов, то получите вердикт Wrong answer.

Чтобы сообщить ответ, выведите строку в формате «! a b» (без кавычек), где $$$a$$$ и $$$b$$$ — найденные вами длины массивов $$$A$$$ и $$$B$$$ соответственно. Ответ не учитывается при подсчёте количества запросов.

Если же невозможно однозначно определить длины массивов, выведите «! -1» (без кавычек). Обратите внимание, что если вы ответите $$$-1$$$ в то время, когда существует последовательность из не более чем $$$250$$$ запросов, которая однозначно определяет длины массивов, вы получите вердикт Wrong answer.

Гарантируется, что существуют такие не противоречащие условию массивы $$$A$$$ и $$$B$$$, для которых вывод интерактора корректен.

Интерактор не адаптивен, что означает, что ответ известен до того, как участник задаст запросы, и не зависит от запросов, заданных участником.

Если ваша программа сделает более $$$250$$$ запросов, ваша программа должна немедленно завершиться, чтобы получить вердикт Wrong answer. В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит читать из закрытого потока.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт «IL» (Idleness limit exceeded). Для сброса буфера используйте:

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

Взломы

В этой задаче взломы отключены.