这是一个交互问题。不要忘记在 C++ 中使用 cout.flush() 或 fflush(stdout) 或其他编程语言中的类似函数打印查询后刷新输出。
一排有$$$n$$$个礼盒,从左到右编号为$$$1$$$到$$$n$$$。众所周知,其中 $$$k$$$ 包含有价值的礼物 - 其他盒子只包含幸运石。所有盒子看起来都一样,只是重量不同。所有装有石头的盒子都具有相同的重量,并且比装有贵重物品的盒子严格重。但贵重的礼物可能会有所不同,因此装有贵重物品的盒子可能有不同的重量。
您最多可以提出 $$$50$$$ 查询(打印答案不算在内)。通过每个查询,您可以比较两个不相交的框子集 $$$a_1, a_2, \dots, a_{k_a}$$$ 和 $$$b_1, b_2, \dots, b_{k_b}$$$ 的总权重。作为回报,您将得到四个结果之一:
- 首先,如果子集 $$$a_1, a_2, \dots, a_{k_a}$$$ 严格更重;
- 第二,如果子集 $$$b_1, b_2, \dots, b_{k_b}$$$ 严格更重;
- EQUAL,如果子集总权重相等;
- 如果查询不正确或超出查询限制,则浪费。
使用这样的查询(或者,也许是直觉)找到带有最小索引的有价值礼物的盒子。
输入
输入由多种情况组成。一开始,您会收到整数 $$$T$$$ ($$$1 \le T \le 500$$$) — 测试用例的数量。
在每个测试用例的开头,您会收到两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le \frac{n}{2}$$$) — 一行中的盒子数量以及包含贵重礼物的盒子数量。
保证盒子的顺序预先固定,并且一次测试中$$$n$$$的总和不超过$$$1000$$$。
互动
以三行打印每个查询。在第一行中,按以下格式打印子集的大小:“? $$$k_a$$$ $$$k_b$$$”,其中 $$$k_a$$$ 和 $$$k_b$$$ ($$$1 \le k_a, k_b \le n$$$; $$$k_a + k_b \le n$$$) — 相应的大小。
在第二行中打印 $$$k_a$$$ 整数 $$$a_1, a_2, \dots, a_{k_a}$$$ ($$$1 \le a_i \le n$$$; $$$a_i \neq a_j$$$ if $$$i \neq j$$$) — 第一个子集中框的索引。
在第三行中打印 $$$k_b$$$ 整数 $$$b_1, b_2, \dots, b_{k_b}$$$ ($$$1 \le b_i \le n$$$; $$$b_i \neq b_j$$$ if $$$i \neq j$$$) — 第二子集中框的索引。
子集不应相交,即。 e. $$$a_i \neq b_j$$$ 对于所有 $$$i$$$ 和 $$$j$$$。
您将收到上述四个回复之一。在 WASTED 的情况下,停止你的程序以避免得到随机判决而不是错误答案。
输出
对于每个测试用例,按以下格式打印所有装有贵重礼物的盒子中的最小索引:“! $$$x$$$”,其中 $$$x$$$ ($$$1 \le x \le n$$$) — 盒子的索引。
示例
输入 #1
2 2 1 - - - FIRST - 5 2 - - - FIRST - - - SECOND - - - EQUAL -
输出 #1
- - ? 1 1 1 2 - ! 2 - ? 1 1 1 2 - ? 2 3 4 2 1 3 5 - ? 1 1 4 5 - ! 1
注意
示例中的附加分隔符“–”仅用于增加示例的可读性。将解决方案发送到系统时,不要在解决方案中打印任何不必要的符号或换行符。
此任务禁止黑客攻击。