Missing Boxes

After a recent order, Takis has ~N~ sealed boxes arranged in a row in his warehouse. Each box contains (in addition to cans of pineapple) a piece of paper with a number from ~1~ to ~N~. Initially, the number on the paper in the first box is ~1~, the number in the second box is ~2~, and so on.

Giannis decided to play a prank on Takis. He took some of the boxes, say ~K~ boxes, and moved them to his own warehouse. Then, he rearranged the remaining ~M~ boxes in Takis's warehouse (obviously, ~K + M = N~) so that it would not be possible to tell by looking which boxes were missing.

As soon as Takis returned to his warehouse, he immediately realized that something was wrong. Knowing Giannis well, he is certain, and you can be certain too, that Giannis did not change the relative order of the boxes he left in the warehouse and did not take the ~N~-th box, since it was much heavier than the others.

Based on these assumptions and with your help, Takis wants to figure out which boxes are missing from his warehouse. For this purpose, you can ask Takis to open any box, tell you the number it contains, and seal it again. In order to keep the boxes in the best possible condition, Takis is willing to do this at most ~Q~ times in total.

Interaction

At the beginning of your program's execution, you must read the integer ~M~ from standard input (missing.in): the number of boxes that remained in Takis's warehouse.

Then, you may make at most ~Q~ queries, each asking Takis to tell you the number inside a box. To make a query, you must print a line to standard output (missing.out) containing a question mark (the character ~?~), a space, and an integer: the position of the box. The positions are numbered from ~1~ to ~M~. Then, you must read from standard input (missing.in) the number Takis saw inside the box.

If you print an invalid query or exceed the limit of ~Q~ queries, you will receive the number ~-1~ from standard input instead of an answer, and you must terminate your program immediately. Otherwise, the system may report an incorrect failure verdict, such as Time Limit Exceeded.

Once you have found the numbers of the missing boxes, you must print a line to standard output (missing.out) containing an exclamation mark (the character ~!~), followed by a space, the number ~K~, and the ~K~ required numbers in increasing order. Note that the answer does not count as a query. After each output, whether it is a query or the final answer, you must flush the standard output buffer using one of the following commands:

fflush(stdout);

std::cout.flush();

std::cout << std::flush;

Sample Interaction:

Input:

3
4
3

Output:

? 2
? 1
! 3 1 2 5

Explanation:

Suppose the three boxes Giannis left for Takis contain the numbers ~[3,\;4,\;6]~ (our solution does not know this yet). We ask Takis to open the second box; he tells us that it contains the number ~4~ and seals it again. Then, we point him to the first box, and he tells us that it contains the number ~3~ and seals it again. At this point, we assume that we have found three missing numbers, namely ~1~, ~2~, and ~5~. Note that based on these queries, we could not be certain of the answer, so we simply guessed it.

Constraints

• ~1 \le M < N \le 5.000~
• ~0 \le N - M \le 50~
• The grader is non-adaptive.

Subtasks:

1. (13 points) ~Q = 5.000~
2. (29 points) ~Q = 420~, ~N - M = 1~
3. (18 points) ~Q = 420~, the numbers of the boxes missing from Takis's warehouse form a contiguous interval.
4. (17 points) ~Q = 660~
5. (23 points) ~Q = 420~

Notes:

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec.
• Maximum available memory: ~64~ MB.

Warning: The answer may exceed ~2^{32}~ and, in general, you may need to perform operations with numbers larger than those that can be represented by the basic int type. Also, make sure to read the input and print the output efficiently in problems that require it.