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

Брат профессора Р. доктор Р. является фармацевтом и работает в одной из аптек Киберславля. Сегодня ему в аптеку пришла партия из $$$N$$$ баночек с таблетками лекарства для укрепления памяти, в каждой баночке $$$N$$$ таблеток. Однако случилась беда: выяснилось, что все таблетки в одной из баночек оказались поддельными. Известно, что каждая таблетка с настоящим лекарством весит $$$500$$$ миллиграмм, а каждая поддельная таблетка весит $$$501$$$ миллиграмм. У доктора Р. есть точные весы, которые показывают суммарный вес таблеток, которые на них положили. Доктор Р. хочет за одно взвешивание узнать, в какой баночке лежат фальшивые таблетки. Чтобы это было удобнее сделать, он пронумеровал баночки числами от $$$1$$$ до $$$N$$$, однако так и не придумал, как правильно сделать одно взвешивание. Доктор попытался обратиться с этим вопросом к брату, однако тот уехал на научную конференцию и оказался недоступен. Поэтому доктор Р. просит вас помочь ему определить баночку с фальшивыми таблетками.

Сначала на вход вашей программе подаётся число $$$N$$$ $$$(1 \le N \le 10^5)$$$ – количество баночек с таблетками.

После этого ваша программа может делать запрос:

1. В первой строке нужно вывести $$$K$$$ $$$(1 \le K \le N)$$$ – количество открываемых баночек.
2. В следующих $$$K$$$ строках нужно вывести в выходной поток пары чисел $$$x~y$$$ $$$(1 \le x \le N, 1 \le y \le N)$$$, где $$$x$$$ – номер баночки, $$$y$$$ – количество таблеток, которые кладутся на весы. Никакая баночка не должна быть указана дважды.

В качестве ответа на запрос нужно будет считать число – суммарный вес таблеток в миллиграммах, который показали весы.

После сделанного запроса вам нужно будет определить номер баночки с фальшивыми таблетками. Для этого нужно будет вывести в выходной поток в отдельной строке «$$$!~M$$$», где $$$M$$$ – номер баночки, в которой, по вашему мнению, находятся фальшивые таблетки.

Если ваша программа сделает более 1 запроса или задаст некорректный запрос (например, запросит номер баночки или количество таблеток большее $$$N$$$), она получит любой вердикт, отличный от «Accepted».

После каждого действия вашей программы выводите символ перевода строки. После вывода очередной строки обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию «fflush(stdout)», в Pascal «flush(output)» на Java и Kotlin вызов «System.out.flush()» и «stdout.flush()» для языка Python.