H. 弦论

内存限制:256 MiB 时间限制:2000 ms 题目类型:交互

题目描述

本题为交互题,请确保你已经完成了交互题测试或了解交互题怎么做,监考人员不会回答任何关于如何做交互题的问题

kuro最近在学习巧克力物理学课程时,老师在解释弦论(String theotry)的相关内容时,提到了下面这个问题。

个隐藏的字符串,仅由小写英文字母组成,总长为,每次操作你可以进行一次询问,询问某个字符串在所有隐藏的字符串中作为前缀共出现了多少次,你可以进行最多次交互,最后,你需要回答最长的字符串是什么(回答的次数不计入询问次数,如果有多个答案,你可以选择任何一种作为回答)。

根据惯例,kuro应该不会这个问题,会来求助你。

如果我们说一个长度为的字符串是另一个字符串的前缀,那么应该满足的长度小于或等于的长度,且对于所有的,.

输入格式

第一行为两个整数,表示字符串数量和字符串总长。

交互

要进行询问,请按以下格式输出一行(不含引号)

"? s"

代表你需要询问的串,注意,s的长度应不大于200!

此时会输入一个整数,代表在所有隐藏的字符串中作为前缀串共出现的次数.

要回答答案,请按以下格式输出一行(不含引号),如果有多个答案,你可以选择任何一种作为回答。

"! s"

代表你的答案,注意,s的长度应不大于200!

此时会输入一个整数,若,你的回答正确;若,你的回答错误.

若在任何时候输入的数为-1,说明你的询问超出次数/询问不合法/回答不合法/答案错误/其他输入错误,此时,你需要直接退出程序,接收到Wrong Answer。否则,你可能会得到任意一种错误类型作为回应

输出询问或回答后,不要忘记输出换行并刷新缓存区。否则,您可能会收到 Time limit exceeded 判定。为此,请使用:

在 C++ 中 fflush(stdout)或 cout.flush()

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

对于其他语言,请参阅其他语言的文档。

交互器不是自适应的,这意味着在参与者提出查询之前就有确定答案,并且不依赖于参与者提出的询问。

样例

注意:双斜杠表示注释,双斜杠后的内容实际上并不会输入,你也不需要输出

输入 #1

3 9//字符串个数 总长度
3//第一次回答
2//第二次回答
1//答案正确

输出 #1

? a//第一次询问
? aa//第二次询问
! aba//回答答案,也可以回答aaa或aab

隐藏的字符串为"aaa","aba"和"aab"

输入 #2

4 10//字符串个数 总长度
4//第一次回答
3//第二次回答
2//第三次回答
1//第四次回答
1//答案正确

输出 #2

? a//第一次询问
? aa//第二次询问
? aaa//第三次询问
? aaaa//第四次询问
! aaaa//回答答案

隐藏的字符串为"a","aa","aaa"和"aaaa"

注意:样例仅举出一种可能交互情况,不代表一定要按照样例进行交互