众所周知，中央情报局（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 | 14 | $1 \le N \le 1\,000$，$Q = \frac{N^2}{4}$，整个密码是一个合法的括号序列。 |
| 2 | 7 | $1 \le N \le 1\,000$，$Q = \frac{N^2}{4}$ |
| 3 | 57 | $1 \le N \le 100\,000$，$Q = N - 1$，整个密码是一个合法的括号序列。 |
| 4 | 22 | $1 \le N \le 100\,000$，$Q = N - 1$ |
样例
样例输入 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（()是合法的括号序列）。 - 最终输出
! ((()))，成功推导密码。