CF1292E Rin and The Unknown Flower

[MisoilePunch♪ - 彩](https://www.youtube.com/watch?v=5VleIdkEeak) 这是一个交互题！ 在 A.R.C. Markland-N 的隐秘办公室的某个普通日子，Rin 收到了一件由探险队长 Sagar 赠送的神器。 经过多次分析，她现在意识到这个神器中包含着一种奇异花朵的数据，这种花朵在新纪元之前就已经存在。然而，关于其化学结构的信息被严重加密了。 这种花朵的化学结构可以表示为一个字符串 $p$。从未加密的文件中，Rin 已经知道该字符串的长度 $n$，并且她还可以确定该字符串至多包含三种不同的字母：“C”（代表碳）、“H”（代表氢）和“O”（代表氧）。 在每一步，Rin 可以向神器的终端输入一个任意长度的字符串 $s$，神器会返回 $s$ 作为 $p$ 的子串出现的所有起始位置。 然而，神器的能量有限，且无法以任何方式充电，因为该技术过于古老，无法与当前 A.R.C. 的任何设备兼容。具体来说： - 神器仅有 $\frac{7}{5}$ 单位的能量。 - 每当 Rin 输入一个长度为 $t$ 的字符串 $s$ 时，神器会消耗 $\frac{1}{t^2}$ 单位的能量。 - 如果能量降至零以下，任务将立即失败，神器将永远熄灭。 由于神器既珍贵又脆弱，Rin 对破解最终数据感到非常紧张。你能帮她一把吗？

交互从一个整数 $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$）表示匹配字符串 $s$ 的子串的起始位置。 当你确定字符串 $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() - 其他语言请参考相关文档。

见输入格式说明。

请注意，示例交互中包含了额外的空行以便于阅读。实际交互中不会有任何空行，你也不应输出任何额外的空行。 由 ChatGPT 4.1 翻译