Description

这是一道交互题。

有 $n$ 枚硬币排成一行，从左到右编号为 $1$ 到 $n$。

其中恰好有 $k$ 枚（$k<n$）是假币，其余 $(n-k)$ 枚是真币。假币比真币轻，且所有真币重量相同，而假币的重量可能不同。已知假币是连续的，即它们的编号为 $p, p+1, \dots, (p+k-1)$。

你需要找出最左侧假币的编号。可以通过称重操作来获取信息：选择两个不相交的硬币集合，比较它们的重量，判断哪个集合更重或两者重量相同。

交互协议

第一行包含三个整数 $n$、$k$、$g$（$1 \le k < n \le 10^4$，$0 \le g \le 6$）——分别表示硬币总数、假币数量和测试块编号。

要执行称重请求，输出 "$\texttt{?}$ $s_1$ $s_2$ $a_1$ $a_2$ $\dots$ $a_{s_1}$ $b_1$ $b_2$ $\dots$ $b_{s_2}$"，其中 $s_1$ 和 $s_2$ 表示待称重集合的大小，数组 $a$ 和 $b$ 分别表示属于第一个和第二个集合的硬币编号。

作为响应，评测程序会输出一个整数 $x$（$x \in \{0,1,2\}$）。如果 $x = 1$，表示第一个集合比第二个重；如果 $x = 2$，表示第二个集合比第一个重；如果 $x = 0$，表示两者重量相同。

如果请求无效（例如超过最大请求次数或参数非法），评测程序会输出 $\texttt{-1}$ 并终止程序。此时，你的程序应终止运行，否则会收到 $\texttt{Wrong Answer}$ 的判定。

每次输出后务必调用 $\texttt{flush}$ 方法。可以使用以下方式：

• C++：$\texttt{fflush(stdout)}$、$\texttt{cout << endl}$ 或 $\texttt{cout.flush()}$；
• Java：$\texttt{System.out.flush()}$；
• Pascal：$\texttt{flush(output)}$；
• Python：$\texttt{sys.stdout.flush()}$；
• 其他编程语言请查阅相关文档。

提交答案时，输出一行 "$\texttt{!}$ $p$"，其中 $p$（$1 \leq p \leq n$）是最左侧假币的编号。

Input Format

见交互协议。

Output Format

见交互协议。

4 1 0

0

0

2

? 1 1 1 2

? 1 1 2 4

? 1 1 3 4

! 3

Hint

定义 $q$ 为某个测试块中允许的最大称重查询次数。

• （$5$ 分）：$n \le 16$，$q=16$；
• （$9$ 分）：$k=1$，$q=16$；
• （$7$ 分）：$k=1$，$q=11$；
• （$16$ 分）：$k \le 16$，$q=11$；
• （$9$ 分）：所有假币重量相同，$q=11$；
• （最多 $54$ 分）：$q=300$。设实际使用的称重次数为 $c$，若 $c \le 9$，得 $54$ 分；否则得 $\lfloor 54 \cdot \max(-0.0004 \cdot c + 0.3134, 0.018 + \frac{9.0773}{c}) \rfloor$ 分。

以下是计算最后一个测试块得分的 C++ 代码（基于称重次数 $c$）：

((c <= 9) ? 54 : int(54 * (max((-0.0004 * c + 0.3134), (0.018 + 9.0773 / c)))))

评分表

$$\begin{array}{|c|c|c|c|c|c|} \hline c \leq 17 & \text{得分} & 18 \leq c \leq 27 & \text{得分} & 28 \leq c \leq 300 & \text{得分} \\ \hline \leq 9 & 54 & 18 & 28 & 28 & 18 \\ 10 & 49 & 19 & 26 & 29-30 & 17 \\ 11 & 45 & 20 & 25 & 31-42 & 16 \\ 12 & 41 & 21 & 24 & 43-89 & 15 \\ 13 & 38 & 22 & 23 & 90-135 & 14 \\ 14 & 35 & 23 & 22 & 136-181 & 13 \\ 15 & 33 & 24 & 21 & 182-227 & 12 \\ 16 & 31 & 25 & 20 & 228-274 & 11 \\ 17 & 29 & 26-27 & 19 & 275-300 & 10 \\ \hline \end{array}$$