There are coins arranged in a row and numbered from to from left to right.
Exactly () of these coins are fake, and the other coins are real. The fake coins are lighter than the real ones. All real coins have the same weight, while fake coins may have different weights. It is also known that the fake coins are , that is, they have indexes .
You need to find the number of the leftmost fake coin. You can use weighing, which is similar to weighing on a two-pan balance scale: select two sets of non-intersecting coins and find out which set weighs more, or that the sets weigh the same.
Interactive Protocol
The first line contains three integers , , (, ) - the total number of coins, the number of fake coins, and the test block number, respectively.
To perform the weighing request, output " ", where and denote the sizes of the sets being weighed, and the arrays and denote the numbers of the coins belonging to the first and second sets, respectively.
In response to the request, the jury program will output a single integer (). If , then the first set is heavier than the second; if , then the second set is heavier than the first; if , then the sets have the same weight.
If the request is invalid (i.e., the maximum number of requests has been exceeded or the request parameters are invalid), the jury program will output and terminate. In this case, terminate your program to receive the verdict .
Be sure to call the method after outputting each line. You can use:
, , or in ;
in ;
in ;
in ;
consult the documentation for other programming languages.
To give the answer, output a single line in the format " ", where () is the number of the leftmost fake coin.
输入格式
See Interactive Protocol.
输出格式
See Interactive Protocol.
样例
样例输入 1
4 1 0
0
0
2
样例输出 1
? 1 1 1 2
? 1 1 2 4
? 1 1 3 4
! 3
数据范围与提示
Let's define as the maximum number of weighing queries you can make in the tests of a certain block.
( points): , ;
( points): , ;
( points): , ;
( points): , ;
( points): all fake coins have the same weight, ;
(up to points): . Let the maximum number of weighings used be . If , you will get points, otherwise you will get points.
Here is the code that computes the number of points for the last block of tests depending on the number of weighings used:
((c <=9)?54:int(54*(max((-0.0004* c +0.3134),(0.018+9.0773/ c)))))
