CF1491F.Magnets

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 -.

这是一个交互式问题。

小野坂早苗正在玩磁铁。她意识到其中一些磁铁已经消磁，因此很想找出这些消磁的磁铁。

共有 $n$ 个磁铁，其类型为以下三种之一：

• N
• S
• - — 这些磁铁已消磁。

注意：你事先并不知道这些磁铁的类型。

你拥有一台可测量磁铁间作用力的仪器，最多可使用 $n+\lfloor \log_2n\rfloor$ 次。

你可以将若干磁铁放入仪器的左侧，再将若干磁铁放入右侧（启动仪器）。显然，每个磁铁在单次查询中至多只能放在一侧（你不必使用全部磁铁），但同一磁铁可在不同查询中重复使用。

随后，仪器会返回这些磁铁之间产生的作用力。形式化地，设左侧有 $n_1$ 个 N 型磁铁、$s_1$ 个 S 型磁铁，右侧有 $n_2$ 个 N 型磁铁、$s_2$ 个 S 型磁铁，则它们之间的作用力为 $n_1n_2+s_1s_2-n_1s_2-n_2s_1$。请注意，该作用力是一个带符号的值。

然而，若作用力的绝对值严格大于 $n$，仪器将会彻底损坏。

你需要在不损坏仪器的前提下，找出所有类型为 - 的磁铁（即所有已消磁的磁铁）。

注意：交互器是非自适应的。磁铁的类型在交互开始前即已固定，且不会随查询而改变。

题目保证：至少有 $2$ 个磁铁的类型不是 -，且至少有 $1$ 个磁铁的类型为 -。

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

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

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.

样例中的空行仅为帮助你更好地理解交互过程，你无需输出这些空行。

在样例中，磁铁的类型为 NN--。

首先，你将第三块磁铁放在左侧，第四块磁铁放在右侧。这两块磁铁的类型均为 -，因此不产生任何作用力。

接着，你将第一块磁铁放在左侧，第二块和第三块磁铁放在右侧。第三块磁铁的类型为 -，而其余两块磁铁的类型均为 N，因此产生的作用力为 $1$。

在接下来的两次查询中，作用力均为 $0$，因为右侧仅有一块类型为 - 的磁铁。

由此可确定，类型为 - 的磁铁是第三块和第四块，因此应输出 ! 2 3 4 并退出。