众所周知，中央情报局（CIA）负责收集、处理和分析国家安全信息。人们还怀疑他们拥有相当庞大的常用电脑密码库，并且正在开发一些非常先进的工具，能够攻破受密码保护的计算机系统。

风水轮流转，现在你的任务是攻破 CIA 服务器的安全防御。祝你好运！

当然，他们非常清楚人类在想出密码时所使用的典型模式，因此尝试诸如 123456、password、1q2w3e4r 或 welcome 之类的密码是徒劳的。幸运的是，我们发现了一些可能对你有用的信息。

具体来说，他们的主密码恰好由 $N$ 个字符组成，其中 $N$ 是一个偶数。这些字符中恰好有一半是左括号（(），另一半是右括号（)）。此外，他们的工程师没有使用常见的“忘记密码？”功能，而是决定向健忘的管理员开放一个 API。通过该 API，管理员最多可以执行 $Q$ 次查询，询问“密码中从第 $a$ 个字符到第 $b$ 个字符的区间是否是合法的括号序列”。

括号序列的合法性归纳定义如下：

• () 是一个合法的括号序列。
• 如果 $A$ 是一个合法的括号序列，那么 ($A$) 也是一个合法的括号序列。
• 如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是一个合法的括号序列。

交互

这是一道交互题。你的程序必须与主办方编写的程序进行通信，该程序模拟了题目描述中虚构的不安全 CIA 服务器的功能。

在开始交互之前，你的程序应该从标准输入中读取一个偶数 $N$ 和一个整数 $Q$。这两个数字的含义已在题目描述中说明。

之后，你的程序可以通过向标准输出写入来发送查询请求。每个查询必须单起一行，格式为 ? a b，其中 $1 \le a \le b \le N$。在写入每个查询后，你的程序应当刷新输出缓冲区（flush），并从标准输入中读取答案。如果密码中从第 $a$ 个字符开始到第 $b$ 个字符结束的区间构成一个合法的括号序列，则答案为 1。否则，答案为 0。你的程序最多可以进行 $Q$ 次此类查询。

在你的程序推导出秘密密码后，应当向标准输出写入一行，格式为 ! x1x2...xN，其中字符 $x_1, x_2, \dots, x_N$ 表示秘密密码的字符。之后，你的程序应当再次刷新输出缓冲区，并正常结束运行。

注意：你可以在评测系统中下载示例源代码，该代码展示了如何正确与 CIA 服务器进行交互，包括如何刷新输出。

子任务

样例

样例输入 1

6 9
1
0
0
1
1

样例输出 1

? 1 6
? 1 2
? 2 4
? 2 5
? 3 4
! ((()))

说明 1

在这个样例中，秘密密码是 ((()))，长度为 $6$，程序最多可以询问 $9$ 次。

• 读入 $N = 6, Q = 9$。
• 询问 ? 1 6，得到回复 1（整个密码是一个合法的括号序列）。
• 询问 ? 1 2，得到回复 0（(( 不是合法的括号序列）。
• 询问 ? 2 4，得到回复 0（(() 不是合法的括号序列）。
• 询问 ? 2 5，得到回复 1（(()) 是合法的括号序列）。
• 询问 ? 3 4，得到回复 1（() 是合法的括号序列）。
• 最终输出 ! ((()))，成功推导密码。