Find a Gift

题意翻译

这是一道**交互题**。当然,在输出询问之后不要忘记**刷新缓冲区**(比如使用 `fflush(stdout)` 或 `cout.flush()`)。 ## 题目描述 一共有 $n$ 个盒子,编号由 $1$ 至 $n$,每个盒子内只有一件东西,它不是石头就是礼物。 每个盒子都有一个重量。所有装有石头的盒子**一样重**,但是装有礼物的盒子**不保证重量相等**。已知所有装有礼物的盒子重量都**严格小于**装有石头盒子的重量。 您已知盒子个数 $n$ 和含有礼物的盒子数量 $k$,需要找到**编号最小**含有礼物盒子的编号。当然您需要通过一些询问来得到结果。 ## 输入格式 **本题包含多组数据**。 输入的第一行是一个正整数 $T$,表示数据组数。 对于每一组数据: 一行二个整数 $n$ 和 $k$,分别表示盒子个数与含有礼物的盒子个数。 _接下来的输入中将包括此数据中程序询问的询问结果,详见**询问、询问结果与回答格式**部分。_ ## 询问、询问结果与回答格式 ### 询问 每次询问您需要给出二个由盒子编号组成且**不重叠**的集合 $A\{a_1,a_2,\dots,a_{k_a}\}$ 与 $B\{b_1,b_2,\dots,b_{k_b}\}$,其大小分别为 $k_a$ 与 $k_b$。在这之后,交互系统会给出二集合所代表盒子重量和的大小关系。 对于每一组数据,您有 $50$ **次**询问的机会(当然回答并不会消耗一次机会)。对于每一次询问: 第一行一个字符 `?` 和集合大小 $k_a$,$k_b$,三者间由空格分开(如 `? 18 40`)。 第二行 $k_a$ 个整数 $a_1,a_2,\dots,a_{k_a}$,表示集合 $A$ 中的元素。 第三行 $k_b$ 个整数 $b_1,b_2,\dots,b_{k_b}$,表示集合 $B$ 中的元素。 **输出一次询问之后不要忘了刷新缓冲区**。 ### 询问结果 对于您的程序给出的每一次询问,交互系统将会在标准输入(`stdin`)中给出一个字符串作为结果。 不妨设询问给出的集合 $A$ 所代表的盒子的总重量为 $w_a$,$B$ 的为 $w_b$。则给出的结果是以下四者之一: - `FIRST` 如果 $w_a>w_b$。 - `SECOND` 如果 $w_a<w_b$。 - `EQUAL` 如果 $w_a=w_b$。 - `WASTED` 如果询问不合法(如本组数据询问机会已用尽或、二集合存在重叠部分等)。 _遇到这种情况,请**立即结束程序**以防止出现不可预知的错误。_ ### 回答 每一组数据需要的询问结束后,输出字符 `!` 和答案 $x$(即**编号最小**包含礼物盒子的编号),二者间以空格分隔(比如 `! 91`)。 ## 数据范围 ### 输入数据 - $1 \leq T \leq 500$ - $2 \leq n \leq 10^3$ - 所有数据组中 $n$ 的总和不超过 $10^3$。 - $1 \leq k \leq \frac{n}{2}$ ### 输出数据要求 - $1 \leq x \leq n$ - $1 \leq k_a,k_b \leq n$ - $2 \leq k_a+k_b \leq n$ ## 提示 样例中的符号 `-` 仅占位以表示输入、输出的时间顺序,真正的数据中没有这些符号。

题目描述

This is an interactive problem. Don't forget to flush output after printing queries using cout.flush() or fflush(stdout) in C++ or similar functions in other programming languages. There are $ n $ gift boxes in a row, numbered from $ 1 $ to $ n $ from left to right. It's known that exactly $ k $ of them contain valuable gifts — other boxes contain just lucky stones. All boxes look the same and differ only in weight. All boxes with stones have the same weight and are strictly heavier than boxes with valuable items. But valuable gifts may be different, so the boxes with valuable items may have different weights. You can ask no more than $ 50 $ queries (printing an answer doesn't count). By each query you can compare total weights of two non-intersecting subsets of boxes $ a_1, a_2, \dots, a_{k_a} $ and $ b_1, b_2, \dots, b_{k_b} $ . In return you'll get one of four results: - FIRST, if subset $ a_1, a_2, \dots, a_{k_a} $ is strictly heavier; - SECOND, if subset $ b_1, b_2, \dots, b_{k_b} $ is strictly heavier; - EQUAL, if subsets have equal total weights; - WASTED, if the query is incorrect or the limit of queries is exceeded. Using such queries (or, maybe, intuition) find the box with a valuable gift with the minimum index.

输入输出格式

输入格式


The input consists of several cases. In the beginning, you receive the integer $ T $ ( $ 1 \le T \le 500 $ ) — the number of test cases. At the beginning of each test case, you receive two integers $ n $ and $ k $ ( $ 2 \le n \le 1000 $ , $ 1 \le k \le \frac{n}{2} $ ) — the number of boxes in a row and the number of boxes with valuable gifts. It's guaranteed that the order of boxes is fixed beforehand and that the sum of $ n $ in one test doesn't exceed $ 1000 $ .

输出格式


For each test case print the minimum index among all boxes with a valuable gift in the following format: "! $ x $ " where $ x $ ( $ 1 \le x \le n $ ) — the index of the box. Interaction Print each query in three lines. In the first line print the sizes of subset in the following format: "? $ k_a $ $ k_b $ " where $ k_a $ and $ k_b $ ( $ 1 \le k_a, k_b \le n $ ; $ k_a + k_b \le n $ ) — the corresponding sizes. In the second line print $ k_a $ integers $ a_1, a_2, \dots, a_{k_a} $ ( $ 1 \le a_i \le n $ ; $ a_i \neq a_j $ if $ i \neq j $ ) — indexes of boxes in the first subset. In the third line print $ k_b $ integers $ b_1, b_2, \dots, b_{k_b} $ ( $ 1 \le b_i \le n $ ; $ b_i \neq b_j $ if $ i \neq j $ ) — indexes of boxes in the second subset. The subsets shouldn't intersect, i. e. $ a_i \neq b_j $ for all $ i $ and $ j $ . You'll receive one of four responses described above. In the case of WASTED stop your program to avoid getting random verdict instead of Wrong Answer.

输入输出样例

输入样例 #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

说明

Additional separators "–" in the sample are used only to increase the readability of the sample. Don't print any unnecessary symbols or line breaks in your solution when you send it to the system. Hacks are forbidden in this task.