|Codeforces Round #614 (Div. 1)|
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:
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:
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:
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 4 2 1 2 1 2 0 1
? C ? CH ? CCHO ! CCHH
2 5 0 2 2 3 1 8 1 5 1 5 1 3 2 1 2 1
? 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.