An Array of Coins and Weighing Requests

This is an interactive problem.

There are $n$ coins arranged in a row and numbered from $1$ to $n$ from left to right.

Exactly $k$ ($k<n$) of these coins are fake, and the other $(n-k)$ 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 consecutive, that is, they have indexes $p,p+1,\dots ,(p+k-1)$.

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.

Input

The first line contains three integers $n$, $k$, $g$ ($1\le k<n\le 10^4$, $0\le g\le 6$) - the total number of coins, the number of fake coins, and the test block number, respectively.

Interaction

To perform the weighing request, output "? $s_1$ $s_2$ $a_1$ $a_2$ $\dots$ $a_{s_1}$ $b_1$ $b_2$ $\dots$ $b_{s_2}$", where $s_1$ and $s_2$ denote the sizes of the sets being weighed, and the arrays $a$ and $b$ 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 $x$ ($x\in \{0,1,2\}$). If $x=1$, then the first set is heavier than the second; if $x=2$, then the second set is heavier than the first; if $x=0$, 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 -1 and terminate. In this case, terminate your program to receive the verdict Wrong Answer.

Be sure to call the flush method after outputting each line. You can use:

• fflush(stdout), cout << endl, or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• sys.stdout.flush() in Python;

• consult the documentation for other programming languages.

Output

To give the answer, output a single line in the format "! $p$", where $p$ ($1\le p\le n$) is the number of the leftmost fake coin.

Examples

4 1 0

0

0

2

? 1 1 1 2

? 1 1 2 4

? 1 1 3 4

! 3

Scoring

Let's define $q$ as the maximum number of weighing queries you can make in the tests of a certain block.

1. ($5$ points): $n\le 16$, $q=16$;

2. ($9$ points): $k=1$, $q=16$;

3. ($7$ points): $k=1$, $q=11$;

4. ($16$ points): $k\le 16$, $q=11$;

5. ($9$ points): all fake coins have the same weight, $q=11$;

6. (up to $54$ points): $q=300$. Let the maximum number of weighings used be $c$. If $c\le 9$, you will get $54$ points, otherwise you will get $\lfloor 54\cdot \max (-0.0004\cdot c+0.3134,0.018+\frac{9.0773}{c})\rfloor$ points.

Here is the C++ 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)))))