Description

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.

Input Format

The first line contains two integers $n, Q$.

The next several lines give the answer for each query, one per line.

Output Format

Several lines, representing the queries.

The last line represents the final answer you obtained.

6 9
1
0
0
1
1

? 1 6

? 1 2

? 2 4

? 2 5

? 3 4

! ((())) 

Hint

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.

Translated by ChatGPT 5