310527: CF1846F. Rudolph and Mimic

F. Rudolph and Mimictime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive task.

Rudolph is a scientist who studies alien life forms. There is a room in front of Rudolph with $n$ different objects scattered around. Among the objects there is exactly one amazing creature — a mimic that can turn into any object. He has already disguised himself in this room and Rudolph needs to find him by experiment.

The experiment takes place in several stages. At each stage, the following happens:

• Rudolf looks at all the objects in the room and writes down their types. The type of each object is indicated by a number; there can be several objects of the same type.
• After inspecting, Rudolph can point to an object that he thinks is a mimic. After that, the experiment ends. Rudolph only has one try, so if he is unsure of the mimic's position, he does the next step instead.
• Rudolf can remove any number of objects from the room (possibly zero). Then Rudolf leaves the room and at this time all objects, including the mimic, are mixed with each other, their order is changed, and the mimic can transform into any other object (even one that is not in the room).
• After this, Rudolf returns to the room and repeats the stage. The mimic may not change appearance, but it can not remain a same object for more than two stages in a row.

Rudolf's task is to detect mimic in no more than five stages.

Input

The first line contains one integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

The first line of each test case contains one integer $n$ $(2 \le n \le 200)$ — the number of objects in the room.

The second line of each test case contains $n$ integers $a_1$,$a_2$,...,$a_n$ $(1 \le a_i \le 9)$ — object types.

Interaction

After you have read the description of the input data set, you must make no more than $5$ queries. Reading the input data is considered the beginning of the first stage, and the mimic may already begin to change.

The request is a line. The first character of the line indicates the request type. To remove objects, print "-". After that print the number $k$ — how many objects you want to remove. Then there are $k$ numbers — indexes of objects in their current location. Indexing starts from one. You can remove the mimic, but in this case you will not be able to point to it and will get "Wrong answer" verdict.

In response to the request you will receive a line containing integers — the objects remaining in the room after removal and mixing.

To indicate the position of a mimic, print "!", then print the index of the object that is the mimic.

The task will be considered solved if the position of the mimic is specified correctly.

If you make more than five requests, or make an invalid request, the solution will get "Wrong answer" verdict.

After outputting a query or the answer do not forget to output the end of line and flush the output. Otherwise, you will get "Idleness limit exceeded". 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.

Hacks

You can hack a solution with the following input format.

The first line contains one integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

The first line of each test case contains two integers $n$, $k$ ($2 \le n \le 200, 1 \le k \le n$) — the number of objects and the position of the mimic.

The second line contains of each test case $n$ integers $a_1$, $a_2$,...,$a_n$ ($1 \le a_i \le 9$) – initial array of objects.

ExampleInput

3
5
1 1 2 2 3

2 1 1 2

2 2 2

2

8
1 2 3 4 3 4 2 1

4 3 4 3 2 2 1 3
 
2 3 3 2

5 3 2

2 5

15
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 

1 2 3 4 5 6 7 8 7 9 5 4 3 2 1 

Output

 
 
- 1 5

- 1 3

- 2 1 2

! 1


- 0

- 4 1 3 7 8

- 1 4

- 1 2

! 2


- 0

! 10

Note

Explanation for the first test: initial array is $x_1$, $x_2$, $x_3$, $x_4$, $x_5$. Mimic is in first position.

• Delete the fifth object. After that, the positions are shuffled, and the mimic chose not to change his appearance. Object positions become $x_4$, $x_1$, $x_2$, $x_3$.
• Delete the third objects. The mimic is forced to turn into another object, because it has already been in the form $1$ for two stages. The mimic chose to transform into $2$, the objects are shuffled and become $x_3$, $x_4$, $x_1$.
• Delete the first and second objects. The objects positions become $x_1$. Only the mimic remains, and it remains an object $2$.
• Point to the first element.

题目大意：

这是一个交互式任务。鲁道夫是一名研究外星生命的科学家。他面前有一个房间，里面散布着 $ n $ 个不同的物体。这些物体中有一个模仿者，它可以变成任何物体。模仿者已经在这个房间里伪装了自己，鲁道夫需要通过实验来找到它。

实验分为几个阶段。在每个阶段中，会发生以下情况：

1. 鲁道夫观察房间内所有物体并记录它们的类型。每个物体的类型用一个数字表示，可能有多个相同类型的物体。
2. 观察后，如果鲁道夫确定模仿者的位置，他可以指出。实验结束。鲁道夫只有一次机会，如果他不确定模仿者的位置，他会进行下一步。
3. 鲁道夫可以移除任意数量的物体（可能为零）。然后鲁道夫离开房间，此时所有物体，包括模仿者，都会被混合在一起，它们的顺序会改变，模仿者可以变成任何其他物体（甚至是不在房间里的物体）。
4. 之后，鲁道夫回到房间并重复该阶段。模仿者可能不会改变外观，但它不能连续超过两个阶段保持相同的物体。

鲁道夫的任务是在不超过五个阶段内找到模仿者。

输入输出数据格式：

输入：

第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。

每个测试用例的第一行包含一个整数 $ n $（$ 2 \le n \ \le 200 $）——房间内物体的数量。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, ..., a_n $（$ 1 \le a_i \le 9 $）——物体的类型。

交互：

在读取输入数据集的描述后，您必须进行不超过 5 次的查询。读取输入数据被视为第一个阶段的开始，模仿者可能已经开始变化。

请求是一行。行的第一个字符表示请求类型。要移除物体，请打印 "-"。然后打印数字 $ k $ ——您想移除多少个物体。然后是 $ k $ 个数字——物体在当前位置的索引。索引从一开始。您可以移除模仿者，但在这种情况下，您将无法指出它，并将得到 "Wrong answer" 判决。

对请求的响应将是一行包含整数的字符串——移除和混合后房间内剩余的物体。

要指出模仿者的位置，请打印 "!"，然后打印模仿者物体的索引。

如果正确指定了模仿者的位置，则任务将被视为解决。

如果您进行超过五次请求，或进行无效请求，解决方案将得到 "Wrong answer" 判决。

输出查询或答案后，不要忘记输出换行符并刷新输出。否则，您将得到 "Idleness limit exceeded"。具体操作请参考相应语言的文档。

破解：

您可以使用以下输入格式破解解决方案。

第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。

每个测试用例的第一行包含两个整数 $ n $, $ k $（$ 2 \le n \le 200, 1 \le k \le n $）——物体的数量和模仿者的位置。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, ..., a_n $（$ 1 \le a_i \le 9 $）——初始物体数组。

示例输入输出见原题目描述。题目大意： 这是一个交互式任务。鲁道夫是一名研究外星生命的科学家。他面前有一个房间，里面散布着 $ n $ 个不同的物体。这些物体中有一个模仿者，它可以变成任何物体。模仿者已经在这个房间里伪装了自己，鲁道夫需要通过实验来找到它。 实验分为几个阶段。在每个阶段中，会发生以下情况： 1. 鲁道夫观察房间内所有物体并记录它们的类型。每个物体的类型用一个数字表示，可能有多个相同类型的物体。 2. 观察后，如果鲁道夫确定模仿者的位置，他可以指出。实验结束。鲁道夫只有一次机会，如果他不确定模仿者的位置，他会进行下一步。 3. 鲁道夫可以移除任意数量的物体（可能为零）。然后鲁道夫离开房间，此时所有物体，包括模仿者，都会被混合在一起，它们的顺序会改变，模仿者可以变成任何其他物体（甚至是不在房间里的物体）。 4. 之后，鲁道夫回到房间并重复该阶段。模仿者可能不会改变外观，但它不能连续超过两个阶段保持相同的物体。 鲁道夫的任务是在不超过五个阶段内找到模仿者。 输入输出数据格式： 输入： 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。 每个测试用例的第一行包含一个整数 $ n $（$ 2 \le n \ \le 200 $）——房间内物体的数量。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, ..., a_n $（$ 1 \le a_i \le 9 $）——物体的类型。 交互： 在读取输入数据集的描述后，您必须进行不超过 5 次的查询。读取输入数据被视为第一个阶段的开始，模仿者可能已经开始变化。 请求是一行。行的第一个字符表示请求类型。要移除物体，请打印 "-"。然后打印数字 $ k $ ——您想移除多少个物体。然后是 $ k $ 个数字——物体在当前位置的索引。索引从一开始。您可以移除模仿者，但在这种情况下，您将无法指出它，并将得到 "Wrong answer" 判决。 对请求的响应将是一行包含整数的字符串——移除和混合后房间内剩余的物体。 要指出模仿者的位置，请打印 "!"，然后打印模仿者物体的索引。 如果正确指定了模仿者的位置，则任务将被视为解决。 如果您进行超过五次请求，或进行无效请求，解决方案将得到 "Wrong answer" 判决。 输出查询或答案后，不要忘记输出换行符并刷新输出。否则，您将得到 "Idleness limit exceeded"。具体操作请参考相应语言的文档。 破解： 您可以使用以下输入格式破解解决方案。 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $, $ k $（$ 2 \le n \le 200, 1 \le k \le n $）——物体的数量和模仿者的位置。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, ..., a_n $（$ 1 \le a_i \le 9 $）——初始物体数组。 示例输入输出见原题目描述。