这是一个交互问题。
在某个数据库中,有$$$n$$$个句柄以编号列表的形式存储。您对某个特定句柄 $$$h$$$ 感兴趣,或者更准确地说,对其在此列表中的位置感兴趣。
你可以向数据库询问列表中的位置$$$i$$$,它将返回第$$$i$$$位置的句柄。
所有句柄都是非空字符串,最多包含 $$$20$$$ 小写拉丁字母, 除了第一个 可以是小写或大写拉丁字母。
您知道所有句柄都按字典顺序排序,但问题是不知道大写字母是否被认为小于小写字母。换句话说,您不知道是否所有以大写字母开头的句柄首先出现,然后是以小写字母开头的句柄,反之亦然,即所有以小写字母开头的句柄首先出现,然后是以大写字母开头的句柄。
词典顺序是标准字符串比较的顺序,正式定义如下:
- 如果字符串 $$$s$$$ 和 $$$t$$$ 在某些位置不同,其中最早的是位置 $$$i$$$,则字符串 $$$s$$$ 按字典顺序排在字符串 $$$t$$$ 之前当且仅当 $$$s_i \lt t_i$$$ (例如,对于字符串 猫 和 当前,第一个不同字符的位置是$$$2$$$,并且字符 a 小于字符 u,所以 猫 按字典顺序小于 当前);
- 如果字符串 $$$s$$$ 和 $$$t$$$ 没有包含不同字符的位置,则较短的位置在前。例如,字符串 猫 位于字符串之前 猫.
由于对数据库的访问受到限制,您最多只能对数据库进行 $$$10$$$ 查询。确定您感兴趣的句柄的位置,知道它肯定在列表中。
输入
第一行包含数字 $$$n$$$ 和字符串 $$$h$$$ ($$$1 \le n \le 500$$$) - 列表中的句柄总数以及您正在搜索的句柄。
保证所有句柄都是不超过 $$$20$$$ 个字符的非空字符串,仅由小写拉丁字母组成,第一个字母可能是大写字母。
还保证所有句柄都是排序的、唯一的,并且给定的句柄位于列表中。
互动
要提出问题,请按以下格式输出字符串(不带引号):
- "?我" ($$$1 \le i \le n$$$)
陪审团将返回一个字符串 $$$s$$$ — 列表中第 $$$i$$$ 位置的句柄。
当您准备好打印答案时,按以下格式输出单个字符串(不带引号):
- "!我" ($$$1 \le i \le n$$$)
交互器不是自适应的,这意味着每个测试中的句柄列表都是预先固定的。
如果您的程序询问超过 $$$10$$$ 查询(不包括打印答案)或违反查询格式,评审团将使用字符串“-1“。在这种情况下,您的程序应立即终止以接收以下判决: 错误答案。否则,您可能会收到任意判决,因为您的解决方案将继续从关闭的流中读取。
打印查询后,不要忘记输出换行符并刷新输出。否则,您可能会收到以下判决: 超出空闲限制。为此,请使用 System.out.flush().
示例
输入复制
4 adedalic Bleddest Neon adedalic awoo
输出复制
? 1 ? 2 ? 3 ? 4 ! 3
输入复制
6 tourist jiangly tourist Radewoosh
输出复制
? 1 ? 3 ? 6 ! 3
注意
请注意,示例中添加空格只是为了提高可读性。检查解决方案时,交互器不会输出任何空行。