{"raw_statement":[{"iden":"background","content":"**本题为交互题**。\n\n众所周知，中央情报局的工作是收集，处理和分析国家安全信息。现在他们拥有了大量的计算机密码，并且正在开发一些相当复杂的工具，来破坏受密码保护的系统。\n\n现在，您的任务是破坏中央情报局服务器的安全性。自然，他们很清楚人们在输入密码的时候通常会输入什么东西，因此尝试输入 `123456` , `1q2w3e4r` 或 `Welcome` 肯定是没有用的。幸运的是，我们发现了某些可能对您有用的信息。"},{"iden":"statement","content":"现在已知中央情报局服务器的主密码由 $n$ 个字符（$n$ 为偶数）构成，其中一半是左括号，一半是右括号。一些记性不好的服务器管理员会忘记这个主密码，所以服务器提供了找回密码的工具。管理员最多可以使用 $Q$ 次这个工具，每次使用时都会询问这个密码 $l$ 到 $r$ 位的括号串是否合法。\n\n对于一个括号串合法的定义：\n\n* `()` 是一个合法的括号串。\n* 若 `A` 是一个合法的括号串，那么 `(A)` 也是一个合法的括号串。\n* 若 `A` 与 `B` 都是合法的括号串，那么 `AB` 也是合法的括号串。\n\n现在你需要写出一个程序来模拟管理员找回密码的过程。\n\n在进行交互之前，您的程序应该从输入中读取偶数 $n$ 和整数 $Q$ ，这两个数字的含义见题目描述。\n\n之后，您的程序可以通过向**标准输出**输出来发送查询请求。每个查询必须在单独的行中打印，并采用 `? a b`，其中 $1 \\leq a \\leq b \\leq n$。每个查询之后，您的程序应**清空缓冲区**并从**标准输入**中读取答案。\n\n当你推理出密码时，请在**标准输出**中输出： `! x1 x2 x3 …… xn` 的形式，之后你的程序应**清空缓冲区**并正常终止程序运行。\n"},{"iden":"input","content":"第一行两个整数 $n,Q$。\n\n接下来若干行，每行对于每个查询给出答案。"},{"iden":"output","content":"若干行，表示查询。\n\n最后一行表示最后得出的答案。"},{"iden":"note","content":"### 样例解释\n`? 1 6` 对应的是整个串，当然是合法的。  \n`? 1 2` 对应的是 `((` 不合法。  \n`? 2 4` 对应的是 `(()` 不合法。  \n`? 2 5` 对应的是 `(())` 合法。  \n`? 3 4` 对应的是 `()` 合法。\n\n### 数据规模与约定\n\n**本题采用捆绑测试**\n\n* Subtask 1（14 pts）：$1\\leq n\\leq 1000$，$Q=\\frac{n^2}{4}$，保证整个括号序列合法。 \n* Subtask 2（7 pts）：$1\\leq n\\leq 1000$，$Q=\\frac{n^2}{4}$。 \n* Subtask 3（57 pts）：$1\\leq n\\leq 100000$，$Q=n-1$，保证整个括号序列合法。 \n* Subtask 4（12 pts）：$1\\leq n\\leq 100000$，$Q=n-1$。 \n\n对于 $100\\%$ 的数据，$1\\leq n\\leq 100000$，$n-1\\leq Q$。 \n\n### 说明\n\n翻译自 [Croatian Olympiad in Informatics 2020 D Zagrade](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。"}],"translated_statement":null,"sample_group":[["6 9\n1\n0\n0\n1\n1","? 1 6\n\n? 1 2\n\n? 2 4\n\n? 2 5\n\n? 3 4\n\n! ((())) "]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}