You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

粉色奶龙和啥龙在van游戏

题目

啥龙面前有 $N$ 个仓库取货口，从左到右编号为 $0$ 到 $N-1$ ，每个取货口可以指定输出两种矿物之一： 源矿 或 蓝铁矿。取货口连接着一个传送带系统，会把出货口的输出按照一定顺序打乱并传送到 $N$ 个输出口，但是啥龙并不知道这个顺序。输出口从左到右编号为 $0$ 到 $N-1$，每个输出口前有一个速冻仔。

粉色奶龙会让速冻仔从左到右报数，报数规则如下：

• 最左边的速冻仔报 $0$
• 对于其他速冻仔，如果自己面前的矿物与左边相邻的速冻仔面前的矿物不同，则报左边速冻仔的报数加 $1$；否则报与左边相同的数。

然后粉色奶龙会告诉啥龙最后一个速冻仔报了什么数。

啥龙可以多次进行实验：每次她可以自由设定所有输入口的矿物种类，然后得到最后一个速冻仔的报数。她的目标是确定两个端点输出口（输出口 $0$ 和输出口 $N-1$）对应哪两个取货口。

由于啥龙的智商超群，所以请来了管理员你来狐假虎威帮助她赢得游戏。

交互方式

• 你的程序应首先读取一行包含整数 $N$：仓库取货口的数量。
• 然后，你的程序应与交互器交互。要开始一次实验，你应输出一行以问号 ? 开头，然后是一个长度为 $N$ 的字符串，有 $0$ （原矿）和 $1$ （蓝铁矿）组成，表示你如何设置 $N$ 个取货口的输出。然后，你的程序应读取一个整数 $l$ $(0 \leq l < N)$，即最后一个速冻仔报的数。
• 当你想要回答时，输出一行以感叹号 ! 开头，后面跟着两个整数$A$ 和 $B$ $(0\leq A,B < N)$。为了让你的答案被接受，这必须是对应输出口 $0$ 和输出口 $N-1$ 的取货口编号，顺序不限。之后，你的程序应退出。

交互器是非自适应的，这意味着取货口和输出口的对应关系在交互开始前就已确定。

请确保在每次实验后刷新标准输出，否则你的程序可能会被判定为超时。在 Python 中，只要使用 input() 读取行，输出会自动刷新。在 C++ 中，cout << endl; 除了输出换行外还会刷新；如果使用 printf，请使用 fflush(stdout)。

样例 1

隐藏的对应关系：

在样例 1 中，有 $5$ 个取货口。 第一次实验中，速冻仔（从左到右）面前的矿物分别是 源矿、源矿、蓝铁矿、源矿、蓝铁矿，报的数为 $[0, 0, 1, 2, 3]$，所以交互器输出 $3$。 第二次实验中，速冻仔（从左到右）面前的矿物分别是 蓝铁矿、源矿、蓝铁矿、蓝铁矿、源矿，报的数为 $[0, 1, 2, 2, 3]$，所以交互器输出 $3$。 最后啥龙得出对应输出口 $0$ 和输出口 $N-1$ 的取货口是第 $2$ 和 第 $4$ 个取货口（次序不限），! 2 4 和 ! 4 2 都是可接受的答案。

样例 2

隐藏的对应关系：

在样例 2 中，有 $3$ 个取货口。 第一次实验中，速冻仔（从左到右）面前的矿物分别是 蓝铁矿、蓝铁矿、蓝铁矿，报的数为 $[0, 0, 0]$，所以交互器输出 $0$。 第二次实验中，速冻仔（从左到右）面前的矿物分别是 蓝铁矿、源矿、蓝铁矿，报的数为 $[0, 1, 2]$，所以交互器输出 $2$。 第三次实验中，速冻仔（从左到右）面前的矿物分别是 源矿、源矿、源矿，报的数为 $[0, 0, 0]$，所以交互器输出 $0$。 最后啥龙得出对应输出口 $0$ 和输出口 $N-1$ 的取货口是第 $0$ 和 第 $1$ 个取货口（次序不限），! 0 1 和 ! 1 0 都是可接受的答案。

样例 3

隐藏的对应关系：

在样例 3 中，有 $4$ 个取货口。 第一次实验中，速冻仔（从左到右）面前的矿物分别是 蓝铁矿、源矿、蓝铁矿、源矿，报的数为 $[0, 1, 2, 3]$，所以交互器输出 $3$。 最后啥龙得出对应输出口 $0$ 和输出口 $N-1$ 的取货口是第 $0$ 和 第 $3$ 个取货口（次序不限），! 0 3 和 ! 3 0 都是可接受的答案。

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 30000$
• 你最多可以发起 $30$ 次实验，（输出最终答案不计入实验次数）。如果你超过这个限制，将得到判为 “Wrong Answer”。

详细子任务附加限制及分值如下表所示。