F. Фальшивая монета
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ монет. Вы точно знаете, что одна из них фальшивая и отличается по весу, но неизвестно, на сколько и в какую сторону.

Вы хотите c помощью серии взвешиваний определить, какая же из монет фальшивая. У вас есть весы с двумя чашами. На каждую чашу весов можно класть сколько угодно монет (но количества на первой и второй чашах должны совпадать).

Протокол взаимодействия

Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.

В самом начале вашей программе сообщается единственное число $$$n$$$ ($$$3 \le n \le 1000$$$) — количество монет.

После этого вы можете сделать не более $$$9$$$ взвешиваний. Чтобы провести взвешивание, нужно вывести три строки. В первой строке должен содержаться символ «?», а затем через пробел целое положительное число $$$k$$$ — количество монет, которое вы положите на каждую чашу весов. Во второй строке должны содержаться $$$k$$$ чисел — номера монет, которые вы положите на первую чашу весов. В третьей строке аналогичным образом должны содержаться $$$k$$$ номеров монет, которые вы положите на вторую чашу весов. Все выведенные номера монет во второй и третьей строках должны быть в промежутке от $$$1$$$ до $$$n$$$ и быть различны.

В ответ на такой запрос вам приходит результат взвешивания — один из трех символов «<», «=» или «>».

После того, как вы однозначно установите фальшивую монету, выведите символ «!», а затем через пробел целое число от $$$1$$$ до $$$n$$$ — ее номер. После этого ваша программа должна завершиться.

Пример
Входные данные
6



>



<



=
Выходные данные

? 3
1 2 3
4 5 6

? 2
1 4
2 5

? 1
3
4

! 2
Примечание

Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.

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