Magnets

**官方题面** _这是一个交互题。_ 早苗有 $n$ 块磁石，编号为 $1,2,\cdots,n$。每块磁石的磁极可能是正极，负极，也可能没有磁性。她希望你能帮她找出所有没有磁性的磁石。 万幸的是，你有一台磁力检测仪。你每次可以将每个磁石放在这台机器的左托盘，右托盘或者不放。 机器将会返回此时的磁力强度。设托盘左边有 $n_1$ 个磁石为正极，$s_1$ 个磁石为负极，托盘右边中有 $n_2$ 磁石为正极，$s_2$ 个磁石为负极，则返回的磁力强度为 $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $。 如果一次测试中磁力强度的绝对值大于 $n$，这台机器就会坏掉。 你需要在 $n+\lfloor\log_2n\rfloor$ 次测试内找到所有没有磁性的磁石的编号，同时不能弄坏机器。 **保证存在至少 $2$ 块磁石有磁性且至少 $1$ 块磁石没有磁性。** ------------------------------- 仅一行，包含一个正整数 $T$（$1\leq T\leq 100$），表示数据的组数。 ---------------------------------------- 对于每组数据，你需要先读入一个正整数 $n$（$3\leq n\leq 2000$），代表磁石的数量，保证每组数据的 $n$ 之和不超过 $2000$。 接下来，你可以向交互库提出若干次询问。对于每个询问，你需要输出三行： * 第一行输出 ``? L R``，其中 $L$ 代表放在左托盘的磁石个数，$R$ 代表放在右托盘的磁石个数。 * 第二行输出 $L$ 个数 $a_1,a_2,\cdots,a_L$，代表放在左托盘的磁石编号。 * 第三行输出 $R$ 个数 $b_1,b_2,\cdots,b_R$，代表放在右托盘的磁石编号。 显然，你需要保证 $a_i\neq b_j$。 接下来，你需要刷新缓冲区。 （刷新缓冲区教程） 最后，你需要读入一个整数 $F$，代表这次测试的磁性大小。 如果你已经确定了答案，输出一行 ``! k A`` 表示答案，其中 $k$ 代表没有磁性的磁石数量，$A$ 为一个长度为 $k$ 的序列，代表所有没有磁性的磁石编号。如果这不是最后一组数据，你应该继续处理下一组数据。如果这是最后一组数据，你应该立刻结束你的程序。 **此题中，交互库是固定的。** 每个磁石的状态不随着你的测试而改变。 ------------------------------ 如果你想叉别人，你需要用以下的方式上传数据： 第一行，输入一个正整数 $T$（$1\leq T\leq 100$），表示数据的组数。 接下来输入 $T$ 组数据，每组两行。 第一行输入一个正整数 $n$（$3\leq n\leq 2000$），代表磁石的数量，保证每组数据的 $n$ 之和不超过 $2000$。 第二行输入一个长度为 $n$ 的字符串 $S$，描述每个磁石的磁极。 对于第 $i$ 个字符，如果第 $i$ 个磁石为正极，输出 ``N``，如果第 $i$ 个磁石为负极，输出 ``S``，如果第 $i$ 个磁石没有磁性，输出 ``-``。 你应该保证存在至少 $2$ 块磁石有磁性且至少 $1$ 块磁石没有磁性。 ----------------------------- 在样例中，前两个磁石为正极，后两个磁石没有磁性。 第一次测试中，左托盘和右托盘各有一个没有磁性的磁石，$n_1=s_1=n_2=s_2=0$，因此磁力为 $0$。 第二次测试中，左托盘有一个正极磁石，右托盘有一个正极磁石和一个没有磁性的磁石，$n_1=n_2=1,s_1=s_2=0$，因此磁力为 $1$。 剩余的测试中，右边的托盘都只有一个没有磁性的磁石，因此磁力为 $0$。 因此我们确定了第三个和第四个磁石没有磁力，输出 ``! 2 3 4``。

This is an interactive problem. Kochiya Sanae is playing with magnets. Realizing that some of those magnets are demagnetized, she is curious to find them out. There are $ n $ magnets, which can be of the following $ 3 $ types: - N - S - - — these magnets are demagnetized. Note that you don't know the types of these magnets beforehand. You have a machine which can measure the force between the magnets, and you can use it at most $ n+\lfloor \log_2n\rfloor $ times. You can put some magnets to the left part of the machine and some to the right part of the machine, and launch the machine. Obviously, you can put one magnet to at most one side (you don't have to put all magnets). You can put the same magnet in different queries. Then the machine will tell the force these magnets produce. Formally, let $ n_1,s_1 $ be the number of N and S magnets correspondently on the left and $ n_2,s_2 $ — on the right. Then the force between them would be $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $ . Please note that the force is a signed value. However, when the absolute value of the force is strictly larger than $ n $ , the machine will crash into pieces. You need to find all magnets of type - (all demagnetized ones), without breaking the machine. Note that the interactor is not adaptive. The types of the magnets are fixed before the start of the interaction and do not change with queries. It is guaranteed that there are at least $ 2 $ magnets whose type is not -, and at least $ 1 $ magnet of type -.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

For each test case you should start by reading an integer $ n $ ( $ 3 \leq n \leq 2000 $ ) — the number of the magnets. It is guaranteed that the total sum of all $ n $ over all test cases doesn't exceed $ 2000 $ . After that you can put some magnets into the machine and make a query from the statement. You have to print each query in three lines: - In the first line print "? l r" (without quotes) where $ l $ and $ r $ ( $ 1 \leq l,r < n $ , $ l+r \leq n $ ) respectively denote the number of the magnets you put to left and right. - In the second line print $ l $ integers $ a_1, \dots, a_l $ ( $ 1 \leq a_i \leq n $ , $ a_i \neq a_j $ if $ i \neq j $ ) — the indices of the magnets you put to left. - In the third line print $ r $ integers $ b_1, \dots, b_r $ ( $ 1 \leq b_i \leq n $ , $ b_i \neq b_j $ if $ i \neq j $ ) — the indices of the magnets you put to right. - The same magnet can't be put to both sides in the same query. Formally, you should guarantee that $ a_i \neq b_j $ for any $ i $ and $ j $ . However, you may leave some magnets unused. After printing a query do not forget to output end of line and flush the output. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. After this, you should read an integer $ F $ — the force these magnets produce. Note that if your query is invalid(either the query limit exceeds, the machine crashes or the arguments are invalid), the interactor will terminate immediately. In this case terminate your program to receive verdict Wrong Answer instead of arbitrary verdicts. If you are confident about your answer, use the following format to report it: - "! k A", where $ k $ is the number of magnets you found, and $ A $ is an array consisting of $ k $ different integers from $ 1 $ to $ n $ denoting the indices of the magnets of type - that you found. You may print elements of $ A $ in arbitrary order. - After that, if this is the last test case, you have to terminate your program; otherwise you should immediately continue to deal with the next test case. Note that the interactor is not adaptive. The types of the magnets are fixed before the start of interaction and do not change with queries. Hacks To hack a solution, use the following format: The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases in your hack. Then follow the descriptions of the $ t $ test cases, each printed in two lines: - The first line contains a single integer $ n $ ( $ 3 \leq n \leq 2000 $ ) — the number of magnets. - The second line contains a string $ S $ of length $ n $ consisting of only N, S and -, denoting the magnets' types. - Each of your test case should guarantee that there are at least $ 2 $ magnets whose type is not -, and at least $ 1 $ magnet of type -. Meanwhile, the total sum of $ n $ in all test cases should not exceed $ 2000 $ .

1
4



0



1



0



0

? 1 1
3
4

? 1 2
1
2 3

? 1 1
1
4

? 1 1
1
3

! 2 3 4

The empty lines in the sample are just for you to better understand the interaction process. You're not required to print them. In the sample, the types of the magnets are NN--. At first, you put the third magnet on the left and the fourth one on the right. Both of them have type -, thus no force is produced. Then you put the first magnet on the left and the second and third one on the right. The third magnet has type -, while the other two magnets are of type N, so the force produced is $ 1 $ . In the following two queries, the force is $ 0 $ since there is only a magnet with property - on the right. Then we can determine that the magnets of type - are the third and the fourth one, so we should print ! 2 3 4 and exit.