猜字符串

题目背景

这是一道交互式题目。

评测程序想好了一个长度为 $n$ 的字符串 $s$，字符串只由字符 a、b、c 组成。你的程序需要猜出这个字符串。

为了猜出字符串，你的程序可以进行若干次询问。每次询问包含一个整数 $i$ 和一个长度为 $2$ 的小写英文字母串 $u$。评测程序会回答下面两个命题中有多少个为真：

也就是说，回答可能是 $0,1,2$。

你需要在不超过

次询问内猜出字符串。这里 $\lceil x\rceil$ 表示向上取整。

交互协议

本题一次程序运行中可能包含多局游戏。保证每次运行的游戏数量不超过 $100$。

每局游戏开始时，你的程序需要从标准输入读入一个整数 $n$。

• 若 $n=0$，表示所有游戏已经结束，你的程序应当立刻退出；
• 否则，表示新一局游戏开始，隐藏字符串长度为 $n$，其中 $2\le n\le 100$。

在一局游戏中，你的程序可以进行不超过 $\left\lceil \frac{4n}{3}\right\rceil$ 次询问。

询问

若要进行一次询问，输出一行：

? i u

其中：

• $1\le i\le n-1$；
• $u$ 是一个长度为 $2$ 的小写英文字母串。

随后，你的程序需要从标准输入读入一个整数 $a$，其中 $a\in\{0,1,2\}$，表示下面两个命题中成立的个数：

回答

当你的程序已经确定隐藏字符串后，输出一行：

! s

其中 $s$ 是你猜出的长度为 $n$ 的字符串。

输出最终答案不计入询问次数。输出答案后，你的程序应继续读取下一局游戏的 $n$，直到读到 $n=0$ 为止。

重要说明

评测程序可以是自适应的。也就是说，它不一定在一开始固定一个字符串，而是可以根据你的询问动态选择回答，只要始终存在至少一个字符串与此前所有回答一致即可。

因此，如果你的程序输出的字符串不是评测程序最终认可的那个字符串，即使它也可能与部分回答一致，也可能得到 Wrong Answer。

每次输出询问或答案后，都必须换行并刷新输出缓冲区。C++ 中可以使用 endl，或者输出 \n 后调用 cout.flush()。

样例

标准输入

3

2

1

1

2

0

标准输出

? 1 ab

? 2 ba

? 2 bb

? 2 bc

! abc

样例说明

样例中的空行只是为了更清楚地展示交互过程。真实交互中不会有这些空行，你也不应该输出空行。每次询问、每次回答后输出一个换行即可。

数据范围

• $2\le n\le 100$；
• 每次运行的游戏数量不超过 $100$；
• 每局最多允许 $\left\lceil \frac{4n}{3}\right\rceil$ 次询问。