This problem is interactive.

Professor R.'s brother, Dr. R., is a pharmacist who works in one of the pharmacies in Cyberslavl. Today, a batch of $$$N$$$ bottles of pills for memory strengthening came to his pharmacy, each bottle contains $$$N$$$ pills. However, trouble happened: it turned out that all the pills in one of the bottles were fake. It is known that each pill with a real medicine weighs $$$500$$$ milligrams, and each fake pill weighs $$$501$$$ milligrams. Dr. R. has accurate scales that show the total weight of the pills on them. Dr. R. wants to find the bottle with fake pills in one weighing. To make it easier, he numbered the bottles from $$$1$$$ to $$$N$$$, but he never figured out how to do one weighing correctly. The doctor tried to address this question to his brother, but he had left for a scientific conference and was unavailable. Therefore, Dr. R. asks you to help him to identify a bottle with fake pills.

First, the number $$$N$$$ $$$(1 \le N \le 10^5)$$$ is given to your program as input – the number of bottles of pills.

After that, your program can make a request:

1. In the first line, you need to print $$$K$$$ $$$(1 \le K \le N)$$$ – the number of bottles to open.
2. In the following $$$K$$$ lines, you need to output to the output stream pairs of numbers $$$x~y$$$ $$$(1 \le x \le N, 1 \le y \le N)$$$, where $$$x$$$ is the number of the bottle, $$$y$$$ is the number of pills that are placed on the scale.

As a response to the request, you need to read the number – the total weight of the pills in milligrams, which the scales showed.

After making a request, you need to determine the number of the bottle with the fake pills. To do this, you need to output "$$$!~M$$$" to the output stream in a separate line, where $$$M$$$ is the number of the bottle with fake pills, according to your opinion.

If your program makes more than 1 request or sets an incorrect request (for example, requests a number of a bottle or a number of pills greater than $$$N$$$), it will receive any verdict other than "Accepted".

After printing a query do not forget to output end of line and flush the output. After the output of another request, be sure to use the stream cleanup functions so that part of your output does not remain in some buffer. For example, in C++ it is necessary to use the function "fflush(stdout)" or "cout.flush()", in Java and Kotlin the call "System.out.flush()" and "stdout.flush()" for Python.