CF1292E.Rin and The Unknown Flower

MisoilePunch♪ - 彩

This is an interactive problem!

On a normal day at the hidden office in A.R.C. Markland-N, Rin received an artifact, given to her by the exploration captain Sagar.

After much analysis, she now realizes that this artifact contains data about a strange flower, which has existed way before the New Age. However, the information about its chemical structure has been encrypted heavily.

The chemical structure of this flower can be represented as a string $p$. From the unencrypted papers included, Rin already knows the length $n$ of that string, and she can also conclude that the string contains at most three distinct letters: "C" (as in Carbon), "H" (as in Hydrogen), and "O" (as in Oxygen).

At each moment, Rin can input a string $s$ of an arbitrary length into the artifact's terminal, and it will return every starting position of $s$ as a substring of $p$.

However, the artifact has limited energy and cannot be recharged in any way, since the technology is way too ancient and is incompatible with any current A.R.C.'s devices. To be specific:

• The artifact only contains $\frac{7}{5}$ units of energy.
• For each time Rin inputs a string $s$ of length $t$, the artifact consumes $\frac{1}{t^2}$ units of energy.
• If the amount of energy reaches below zero, the task will be considered failed immediately, as the artifact will go black forever.

Since the artifact is so precious yet fragile, Rin is very nervous to attempt to crack the final data. Can you give her a helping hand?

Interaction

The interaction starts with a single integer $t$ ($1 \le t \le 500$), the number of test cases. The interaction for each testcase is described below:

First, read an integer $n$ ($4 \le n \le 50$), the length of the string $p$.

Then you can make queries of type "? s" ($1 \le |s| \le n$) to find the occurrences of $s$ as a substring of $p$.

After the query, you need to read its result as a series of integers in a line:

• The first integer $k$ denotes the number of occurrences of $s$ as a substring of $p$ ($-1 \le k \le n$). If $k = -1$, it means you have exceeded the energy limit or printed an invalid query, and you need to terminate immediately, to guarantee a "Wrong answer" verdict, otherwise you might get an arbitrary verdict because your solution will continue to read from a closed stream.
• The following $k$ integers $a_1, a_2, \ldots, a_k$ ($1 \le a_1 \lt a_2 \lt \ldots \lt a_k \le n$) denote the starting positions of the substrings that match the string $s$.

When you find out the string $p$, print "! $p$" to finish a test case. This query doesn't consume any energy. The interactor will return an integer $1$ or $0$. If the interactor returns $1$, you can proceed to the next test case, or terminate the program if it was the last testcase.

If the interactor returns $0$, it means that your guess is incorrect, and you should to terminate to guarantee a "Wrong answer" verdict.

Note that in every test case the string $p$ is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might 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 the documentation for other languages.

Hacks

For hack, use the following format. Note that you can only hack with one test case:

The first line should contain a single integer $t$ ($t = 1$).

The second line should contain an integer $n$ ($4 \le n \le 50$) — the string's size.

The third line should contain a string of size $n$, consisting of characters "C", "H" and "O" only. This is the string contestants will have to find out.

MisoilePunch♪ - 彩

这是一个交互式问题！

在 A.R.C. Markland-N 隐蔽办公室的一个寻常日子里，凛收到了一件由探险队长萨加尔交给她的远古遗物。

经过大量分析，她意识到这件遗物中存储着一种奇异花朵的数据——这种花早在“新时代”之前便已存在。然而，关于其化学结构的信息被进行了高度加密。

该花朵的化学结构可表示为一个字符串 $p$。根据随遗物附带的未加密资料，凛已知该字符串的长度 $n$，并且还能推断出该字符串最多仅包含三种不同字符：“C”（代表碳）、“H”（代表氢）和“O”（代表氧）。

在任意时刻，凛均可向遗物终端输入一个任意长度的字符串 $s$，遗物将返回 $s$ 在 $p$ 中作为子串出现的所有起始位置。

但该遗物能量有限，且完全无法充电——因其技术过于古老，与当前 A.R.C. 的任何设备均不兼容。具体而言：

• 遗物初始仅含有 $\frac{7}{5}$ 单位能量；
• 每次凛输入一个长度为 $t$ 的字符串 $s$，遗物将消耗 $\frac{1}{t^2}$ 单位能量；
• 若剩余能量降至零以下，任务将立即失败，遗物将永久黑屏。

由于该遗物极其珍贵又异常脆弱，凛在尝试破解最终数据时非常紧张。你能帮她一把吗？

交互方式

交互以一个整数 $t$（$1 \le t \le 500$）开始，表示测试用例数量。每个测试用例的交互过程如下：

首先，读入一个整数 $n$（$4 \le n \le 50$），即字符串 $p$ 的长度。

随后，你可以发出形如 "? s" 的查询（其中 $1 \le |s| \le n$），以获取 $s$ 在 $p$ 中作为子串的所有出现位置。

发出查询后，你需要读取一行返回结果，该行包含若干整数：

• 第一个整数 $k$ 表示 $s$ 在 $p$ 中作为子串的出现次数（$-1 \le k \le n$）。若 $k = -1$，说明你已超出能量限制或输出了非法查询，此时必须立即终止程序，以确保获得 “Wrong answer” 判定；否则，你的程序将继续从已关闭的流中读取数据，可能导致任意判定结果。
• 接下来的 $k$ 个整数 $a_1, a_2, \ldots, a_k$（满足 $1 \le a_1 < a_2 < \ldots < a_k \le n$）表示所有匹配子串的起始位置。

当你确定字符串 $p$ 后，请输出 "! $p$" 以结束当前测试用例。该查询不消耗任何能量。交互器将返回一个整数 $1$ 或 $0$：若返回 $1$，你可继续处理下一个测试用例；若已是最后一个测试用例，则可直接终止程序。

若交互器返回 $0$，说明你的猜测错误，此时应立即终止程序，以确保获得 “Wrong answer” 判定。

注意：在每个测试用例中，字符串 $p$ 在所有查询开始前即已固定，且不会在查询过程中发生变化，即交互器是非自适应的。

每次输出查询后，务必输出换行符并刷新输出缓冲区；否则可能因空闲超时（Idleness limit exceeded）而被判错。刷新方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参考相应文档。

Hack（数据构造）

对于 hack，需采用如下格式（注意：仅允许 hack 单个测试用例）：

第一行应为一个整数 $t$（$t = 1$）；
第二行应为一个整数 $n$（$4 \le n \le 50$）——即目标字符串的长度；
第三行应为一个长度为 $n$ 的字符串，仅由字符 "C"、"H" 和 "O" 组成。该字符串即参赛者需要还原的目标字符串。

Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

注意，示例交互中包含额外的空行，以便于阅读。实际交互中不包含任何空行，因此你也不应输出任何额外的空行。