P8430 [COI 2020] Zagrade

**This is an interactive problem.** As everyone knows, the job of the Central Intelligence Agency is to collect, process, and analyze national security information. They now have a large number of computer passwords and are developing some fairly complex tools to break into password-protected systems. Now, your task is to break the security of the CIA server. Naturally, they know very well what people usually type when entering passwords, so trying `123456`, `1q2w3e4r`, or `Welcome` is definitely useless. Fortunately, we have discovered some information that may be useful to you.

It is now known that the master password of the CIA server consists of $n$ characters ($n$ is even), with half left parentheses and half right parentheses. Some forgetful server administrators may forget this master password, so the server provides a password recovery tool. The administrator can use this tool at most $Q$ times, and each use queries whether the substring from position $l$ to $r$ is a valid bracket sequence. The definition of a valid bracket sequence: * `()` is a valid bracket sequence. * If `A` is a valid bracket sequence, then `(A)` is also a valid bracket sequence. * If both `A` and `B` are valid bracket sequences, then `AB` is also a valid bracket sequence. Now you need to write a program to simulate the administrator recovering the password. Before interaction starts, your program should read the even integer $n$ and the integer $Q$ from input. The meanings of these two numbers are described above. After that, your program can send query requests by printing to **standard output**. Each query must be printed on a separate line in the form `? a b`, where $1 \leq a \leq b \leq n$. After each query, your program should **flush the buffer** and read the answer from **standard input**. When you have deduced the password, print to **standard output** in the form `! x1 x2 x3 …… xn`. After that, your program should **flush the buffer** and terminate normally.

The first line contains two integers $n, Q$. The next several lines give the answer for each query, one per line.

Several lines, representing the queries. The last line represents the final answer you obtained.

### Sample Explanation `? 1 6` corresponds to the whole string, which is of course valid. `? 1 2` corresponds to `((`, which is invalid. `? 2 4` corresponds to `(()`, which is invalid. `? 2 5` corresponds to `(())`, which is valid. `? 3 4` corresponds to `()`, which is valid. ### Constraints **This problem uses bundled testdata.** * Subtask 1 (14 pts): $1 \leq n \leq 1000$, $Q = \frac{n^2}{4}$, the entire bracket sequence is guaranteed to be valid. * Subtask 2 (7 pts): $1 \leq n \leq 1000$, $Q = \frac{n^2}{4}$. * Subtask 3 (57 pts): $1 \leq n \leq 100000$, $Q = n - 1$, the entire bracket sequence is guaranteed to be valid. * Subtask 4 (12 pts): $1 \leq n \leq 100000$, $Q = n - 1$. For $100\%$ of the testdata, $1 \leq n \leq 100000$, $n - 1 \leq Q$. ### Notes Translated from [Croatian Olympiad in Informatics 2020 D Zagrade](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf). Translated by ChatGPT 5