这是一个多阶段（multi-pass）交互式问题。请记得在每次输出后清空输出缓冲区。你可以使用以下方法清空输出：

• C/C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 和 Kotlin 中的 System.out.flush()；
• Python 中的 sys.stdout.flush()。

Bob 需要猜出 $n$ 个秘密整数，每个整数都在 $0$ 到 $100$ 之间（包含边界）。在正确猜出每个数字后，他会通过在纸条上写下一个 8 字符的二进制字符串来记录它。稍后，他必须从这些纸条中恢复这些数字。然而，每张纸条都可能被翻转了，从而使记录的字符串反转。因此，Bob 必须使用一种编码方式，使得对于任何数字，其编码后的字符串和反转后的字符串都能解码为同一个原始数字。

交互

对于每个测试用例，你的程序将被执行两次。在每一次运行中，你的程序都将作为一个交互式程序进行评测。

第一轮运行

输入的第一行包含两个整数 $r$ ($r = 1$) 和 $n$ ($1 \le n \le 100$)。

接下来，对于这 $n$ 个秘密数字中的每一个：

• 你可以通过提问来确定当前的秘密数字。要进行询问，请输出一行，以 ? 开头，后跟一个空格和一个整数 $x$ ($0 \le x \le 100$)。在清空缓冲区后，读取一个整数 $s \in \{0, 1\}$：

  • 如果 $s = 1$，则秘密数字为 $x$；
  • 如果 $s = 0$，则秘密数字不是 $x$。

• 一旦你确定了该数字，输出一行，以 ! 开头，后跟一个空格和一个仅由 0 和 1 组成的 8 字符字符串。该字符串对该数字进行编码，并将作为纸条存储。清空输出并继续处理下一个秘密数字，如果没有更多的秘密数字，则立即终止程序。

对于每个数字，你最多可以进行 $100$ 次询问。记录纸条不计入询问次数。

第二轮运行

你的程序将在第二轮运行中重新启动。

输入的第一行包含两个整数 $r$ ($r = 2$) 和 $n$。

接下来，对于这 $n$ 张纸条中的每一张：

• 读取一行，包含一个 8 字符的二进制字符串。该字符串要么是某个秘密数字的原始编码，要么是其反转后的字符串。

• 输出一个整数 $y$ ($0 \le y \le 100$) —— 记录在这张纸条上的原始数字。清空输出并继续处理下一张纸条，如果没有更多的纸条，则立即终止程序。

这 $n$ 个字符串正是第一轮运行中输出的那些字符串，但每个字符串都可能以原始字符串或其反转形式出现，且顺序是任意的。

正确性评判

如果满足以下条件，你的程序将通过该测试用例：

• 在第一轮运行中，每个秘密数字都被正确识别（即你最终输出 ! 以及该秘密数字的有效编码）；
• 在第二轮运行中，每个输出的数字都与对应纸条中编码的原始数字相匹配。

提供了一个测试工具以帮助你开发和测试你的程序。

样例

输入样例 1 (第一轮)

1 2
1
0
1

输出样例 1 (第一轮)

? 0
! 00000000
? 0
? 100
! 00001111

输入样例 1 (第二轮)

2 2
11110000
00000000

输出样例 1 (第二轮)

100
0