Rin and The Unknown Flower

题意翻译

**这是一道交互题。** 现在你要破译一段物质链。这个物质链被表示成了一个字符串 $p$ ，其中每个字符可能是`C`（碳）、`H`（氢）或`O`（氧），你已经知道了它的长度 $n$ ，它的下标从 $1$ 开始标号。 你得到了一个来自未来的物质分析机。经过研究，它可以接收一个你输入的字符串 $s$ ，然后它返回 $s$ 在 $p$ 中作为子串出现的所有开头位置。更具体地，令 $p_{l,r}$ 表示由 $p$ 的第 $l$ 个字符到第 $r$ 个字符顺次构成的字符串，则下标 $a$ 被返回当且仅当 $p_{a,a+|s|-1}=s$ 。 但是这个分析机的电量十分微弱。具体来说： - 它目前只剩下 $\frac{7}{5}$ 格电量； - 如果向其中输入一个长度为 $t$ 的字符串 $s$ ，它的电量会立刻减少 $\frac{1}{t^2}$ ； - 如果它的电量小于 $0$ ，将立即停止工作，同时你将会被视为没有完成任务； - 由于这个分析机过于高科技，现有的科技都不能给它充电。 现在请借助这台机器，求出原串 $p$ 。 **交互过程** 每个测试点内包含多组测试数据。首先你要读入一个正整数 $t(1\leq t\leq 500)$ ，表示测试数据的组数。接下来将进行 $t$ 次交互。 在每次交互的开始，你需要读入一个正整数 $n(4\leq n\leq 50)$ ，代表所求串 $p$ 的长度。 接下来你可以提出若干次询问。每次询问你需要向标准输出输出一行 `?` $s$ ，其中$s(1\leq |s|\leq n)$ 是你询问的字符串。 每次询问后你会在标准输入后得到结果。首先你需要读入一个整数 $k(-1\leq k\leq n)$ ，代表返回下标的个数；当 $k=-1$ 时表示能量小于 $0$ 或操作不合法，你需要及时退出程序并接受 `WrongAnswer` 的判断。接下来你需要读入 $k$ 个正整数 $a_1,a_2,...,a_k(1\leq a_1<a_2<...<a_k\leq n)$，表示返回的各个下标。 当你确定答案之后请输出一行 `!` $p$ ，其中 $p$ 代表你认为的答案串 $p$ 。接着你需要再读入一个整数表示结果，如果读入 $1$ 表示答案正确，你可以接着进行下一组测试数据的交互；如果读入 $0$ 表示答案错误，你需要及时退出程序并接受 `WrongAnswer` 的判断。 注意：本题的字符串 $p$ 是在交互开始前便确定好的，不会因为交互过程而改变。 注意：每次输出完后请务必使用`flush`清空缓存。 **Hack** 如果你要$\text{Hack}$，请注意：你只能用单组数据进行$\text{Hack}$。

题目描述

[MisoilePunch♪ - 彩](https://www.youtube.com/watch?v=5VleIdkEeak) 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?

输入输出格式

输入格式

输出格式

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 < a_2 < \ldots < 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.

输入输出样例

输入样例 #1

1
4

2 1 2

1 2

0

1

输出样例 #1

? C

? CH

? CCHO

! CCHH

输入样例 #2

2
5

0

2 2 3

1
8

1 5

1 5

1 3

2 1 2

1

输出样例 #2

? O

? HHH

! CHHHH


? COO

? COOH

? HCCOO

? HH

! HHHCCOOH

说明

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.

题意翻译

**这是一道交互题。** 现在你要破译一段物质链。这个物质链被表示成了一个字符串 $p$ ，其中每个字符可能是`C`（碳）、`H`（氢）或`O`（氧），你已经知道了它的长度 $n$ ，它的下标从 $1$ 开始标号。 你得到了一个来自未来的物质分析机。经过研究，它可以接收一个你输入的字符串 $s$ ，然后它返回 $s$ 在 $p$ 中作为子串出现的所有开头位置。更具体地，令 $p_{l,r}$ 表示由 $p$ 的第 $l$ 个字符到第 $r$ 个字符顺次构成的字符串，则下标 $a$ 被返回当且仅当 $p_{a,a+|s|-1}=s$ 。 但是这个分析机的电量十分微弱。具体来说： - 它目前只剩下 $\frac{7}{5}$ 格电量； - 如果向其中输入一个长度为 $t$ 的字符串 $s$ ，它的电量会立刻减少 $\frac{1}{t^2}$ ； - 如果它的电量小于 $0$ ，将立即停止工作，同时你将会被视为没有完成任务； - 由于这个分析机过于高科技，现有的科技都不能给它充电。 现在请借助这台机器，求出原串 $p$ 。 **交互过程** 每个测试点内包含多组测试数据。首先你要读入一个正整数 $t(1\leq t\leq 500)$ ，表示测试数据的组数。接下来将进行 $t$ 次交互。 在每次交互的开始，你需要读入一个正整数 $n(4\leq n\leq 50)$ ，代表所求串 $p$ 的长度。 接下来你可以提出若干次询问。每次询问你需要向标准输出输出一行 `?` $s$ ，其中$s(1\leq |s|\leq n)$ 是你询问的字符串。 每次询问后你会在标准输入后得到结果。首先你需要读入一个整数 $k(-1\leq k\leq n)$ ，代表返回下标的个数；当 $k=-1$ 时表示能量小于 $0$ 或操作不合法，你需要及时退出程序并接受 `WrongAnswer` 的判断。接下来你需要读入 $k$ 个正整数 $a_1,a_2,...,a_k(1\leq a_1<a_2<...<a_k\leq n)$，表示返回的各个下标。 当你确定答案之后请输出一行 `!` $p$ ，其中 $p$ 代表你认为的答案串 $p$ 。接着你需要再读入一个整数表示结果，如果读入 $1$ 表示答案正确，你可以接着进行下一组测试数据的交互；如果读入 $0$ 表示答案错误，你需要及时退出程序并接受 `WrongAnswer` 的判断。 注意：本题的字符串 $p$ 是在交互开始前便确定好的，不会因为交互过程而改变。 注意：每次输出完后请务必使用`flush`清空缓存。 **Hack** 如果你要$\text{Hack}$，请注意：你只能用单组数据进行$\text{Hack}$。