迪玛什得知曼苏尔向朋友写了一些关于他的非常不愉快的内容,因此他决定不惜一切代价找出他的密码,并查明他到底写了什么。
Mansur 相信他的密码的强度,他表示他的密码 — 是一个长度为 $$$n$$$ 的二进制字符串。他还准备回答迪玛希的以下类型的问题:
Dimash 说出一个二进制字符串 $$$t$$$,Mansur 回答 $$$t$$$ 是否是其密码的子字符串。
帮助迪玛希在不超过 $$$2n$$$ 操作中找到密码;否则曼苏尔就会明白其中的伎俩并停止与他交流。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
互动
在每个测试用例的开头,首先读取 $$$n$$$ ($$$1 \le n \le 100$$$) — 二进制字符串的大小。然后继续猜测。
要猜测每个字符串 $$$s$$$,您最多可以进行以下类型的 $$$2n$$$ 查询:
- “?t”,其中 $$$t$$$ 是一个二进制字符串,例如 ($$$1 \le |t| \le n$$$)。
响应此查询,如果 $$$t$$$ 是 $$$s$$$ 的子字符串,则您将收到 $$$1$$$,否则将收到 $$$0$$$。
收到答案后,按以下格式输出单个字符串:
- "!s",其中 $$$s$$$ 是大小为 $$$n$$$ 的二进制字符串。
之后,继续解决下一个测试用例。
如果您尝试错误或超过 $$$2n$$$ 尝试限制,您将收到 $$$-1$$$ 而不是答案,并得到错误答案的判决。在这种情况下,您的程序应立即终止以避免未定义的判决。
输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到解决方案“挂起”的判决。要刷新缓冲区,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客:
要使用 hack,请使用以下测试格式:
第一行应包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。
每个测试用例的第一行应包含一个数字 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串的长度。第二行应包含大小为 $$$n$$$ 的二进制字符串。
示例
输入 #1
4 3 0 0 1 4 4 2
输出 #1
? 00 ? 000 ? 010 ! 010 ! 1100 ! 0110 ! 10
注意
在第一个示例中,给出了字符串 $$$010$$$。因此,对质疑的答复如下:
"? 00" $$$00$$$ 不是 $$$010$$$ 的子串,所以答案是 $$$0$$$。
"? 000" $$$000$$$ 不是子字符串,所以答案是 $$$0$$$。
"? 010" $$$010$$$ 是一个子字符串,所以答案是 $$$1$$$。
在第二个示例中,字符串为 $$$1100$$$,在第三个示例中为 $$$0110$$$,在第四个示例中为 $$$10$$$。