This is an interactive problem.
At the Caruaru Fair, famous for its clothing stalls, a vendor set aside $$$N$$$ shirts that look identical for a challenge. Among these shirts, $$$N - 1$$$ have exactly the same weight, while one different shirt is heavier than all the others.
You may use a two-pan balance scale. In each weighing, you choose the same number of shirts to place on the left pan and on the right pan. The scale tells whether the left pan was heavier, the right pan was heavier, or both pans had the same weight.
Your goal is to find which shirt is the heaviest using at most $$$8$$$ weighings.
Initially, the interactor prints a line containing an integer $$$N$$$ ($$$2 \leq N \leq 2000$$$), the number of shirts. The shirts are numbered from $$$1$$$ to $$$N$$$.
The interactor is non-adaptive: the heaviest shirt is chosen before the interaction starts and does not change during execution.
Your program may perform weighings. To perform a weighing, print a line in the format
where $$$t \geq 1$$$. The shirts $$$a_1, a_2, \ldots, a_t$$$ will be placed on the left pan, and the shirts $$$b_1, b_2, \ldots, b_t$$$ will be placed on the right pan. All these $$$2t$$$ indices must be distinct and between $$$1$$$ and $$$N$$$.
The interactor will answer with a line containing a single character:
When your program knows which shirt is the heaviest, it must print a line in the format
where $$$p$$$ is the index of the heaviest shirt.
The answer operation does not count as a weighing. Only operations that start with ? are counted, and your program may perform at most $$$8$$$ of them.
After printing any line, your program must flush the output. For example, in C++ you may use cout « endl; or cout.flush().
If your program prints an invalid value, performs more than $$$8$$$ weighings, or answers an incorrect shirt, it will receive the verdict NO - Wrong answer.
4 D E
? 2 1 2 3 4 ? 1 3 4 ! 3
Explanation for example 1
In this example, the heaviest shirt is number $$$3$$$. The program uses two of the $$$8$$$ allowed weighings to determine which shirt is the heaviest.
In the first weighing, shirts $$$1$$$ and $$$2$$$ are placed on the left pan, while shirts $$$3$$$ and $$$4$$$ are placed on the right pan. Since the right pan becomes heavier, the different shirt must be either $$$3$$$ or $$$4$$$.
In the second weighing, the program compares shirts $$$3$$$ and $$$4$$$. Since the left pan becomes heavier, the program concludes that shirt $$$3$$$ is the heaviest.
If, in the second weighing, the right pan had been heavier, shirt $$$4$$$ would be the heaviest.
It is not necessary to use all $$$8$$$ allowed weighings. The program may answer as soon as it determines the index of the heaviest shirt.
