题目描述

译自 COI 2020 T4「Zagrade」

众所周知，CIA 是一个负责收集，处理和分析国家安全情报的机构。他们也被怀疑拥有一个巨大的常用计算机密码库，并且在开发一些十分复杂的计算机密码破解工具。

现在风水轮流转了，你的任务是破解一个 CIA 服务器的安全系统。祝你好运！

他们自然深知一些人们在密码中使用的典型模式串。因此像尝试 $\texttt{123456}$，$\texttt{password}$，$\texttt{1q2w3e4r}$ 或者 $\texttt{welcome}$ 这些密码都是无效的。幸运的是，我们有一些未被发现的信息可能对你有用。

服务器的主密码由恰好 $N$ 个字符组成，这里 $N$ 是一个偶数。恰好一半的字符是左括号（即 $\texttt($），剩下恰好一半的字符是右括号（即 $\texttt )$）。此外，他们的工程师决定暴露一个 API 给健忘的管理员，而不是使用通常的「忘记密码」功能。调用这个 API，管理员可以执行最多 $Q$ 次询问「密码从第 $a$ 个字符到第 $b$ 个字符组成的这个括号序列是否是数学意义上合法的」。

一个括号序列在数学意义上合法被如下递归定义：

• $\texttt{()}$ 是数学意义上合法的括号序列。
• 如果 $A$ 是数学意义上合法的括号序列，则 $\texttt ( A\texttt )$ 也是数学意义上合法的括号序列。
• 如果 $A$ 和 $B$ 是数学意义上合法的括号序列，则 $AB$ 也是数学意义上合法的括号序列。

交互过程

这是一道交互题。你的程序必须与 grader 通信，grader 会像题目描述一样模拟一个虚拟且不安全的 CIA 服务器。

在交互之前，你的程序应当从标准输入中读取一个偶数 $N$ 和整数 $Q$，这两个整数的意义如题目描述。

在此之后，你的程序可以通过输出到标准输出来发送询问。每个询问必须输出到单独一行，格式为「$\texttt ? \ a\ b$」，此处需要保证 $1\le a\le b\le N$。在每次询问输出之后，你的程序都需要刷新标准输出，并从标准输入读取答案。如果答案是 $1$，则代表密码中第 $a$ 个字符到第 $b$ 个字符组成的这个括号序列是数学意义上合法的，否则，答案是 $0$。你的程序最多可以询问 $Q$ 次。

在你的程序已经推断出密码后，需要按「$\texttt ! \ x_1x_2\ldots x_N$」这样的格式输出答案。这里字符 $x_1,x_2,\ldots ,x_N$ 代表密码。在此之后，你的程序需要再次刷新标准输出并停止运行。

评分

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

交互样例