I. 早操

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

题目描述

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

左广大学的学生每天都要排成一列做早操。每个学生的状态可以用一个二进制值表示:1 表示该学生来上了早操,0 表示该学生没来上早操。班长们将这些情况整合成了一个长度为的字符串提交给辅导员以表示每个学生是否来上早操,例如,字符串110011表示第1,2,5,6个同学来上了早操,第3,4个同学没有来早操。

但各班班长虚报了一些人上早操的实际情况。聪明的辅导员通过一些手段得知了班长报上的字符串中有个人的情况是不真实的,他决定使用一种神奇的魔法来找出真实情况,这种魔法可以通过询问一个字符串来得知该字符串与真实情况不同的数目。具体来说,辅导员每次可以询问一个长度为的二进制字符串(只包含 0 和 1),系统会返回该字符串与真实情况的字符串的不同个数(即有多少个位置不同)。辅导员最多可以进行 2000 次询问。辅导员需要通过这些询问,找出真实的二进制串。

辅导员找到了acm集训队,acm集训队决定向你求助。

输入格式

第一行为两个整数,表示二进制字符串长度和错误的个数。

第二行为一个长度为的字符串,表示班长们提交的字符串,保证只由0和1组成。

交互

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

"? s"

代表你需要询问的串,注意,s的长度应等于n!

此时会输入一个整数,代表与真实字符串的不同位置个数.

要回答答案,请按以下格式输出一行(不含引号)。

"! s"

代表你的答案,注意,s的长度应等于n!

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

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

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

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

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

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

如果你的输出非法,也可能返回TLE,此时是因为交互器TLE了

样例

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

输入 #1

6 6//字符串长度 错误个数

111111

0//第一次回答

1//第二次回答

输出 #1

? 000000//第一次询问

? 000100//第二次询问

! 000000//回答答案

班长报上的字符串为111111,实际情况为000000

输入 #2

7 3//字符串长度 错误个数

0001101

4//第一次回答

1//第二次回答

输出 #2

? 0000000//第一次询问

? 1011000//第二次询问

! 1011001//回答答案

班长报上的字符串为0001101,实际情况为1011001

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