It is well known that the Central Intelligence Agency is tasked with gathering, processing and analyzing national security information. It is also suspected that they own quite large collections of commonly-used computer passwords and are developing some quite sophisticated tools that are capable of compromising password-protected computer systems.

The tables have turned, your task is to compromise the security of a CIA server. Good luck!

Naturally, they are well aware of typical patterns that humans produce while coming up with their passwords, so attempts such as 123456, password, 1q2w3e4r or welcome are futile. Luckily, we have uncovered certain pieces of information that might be of use to you.

Namely, their master password consists of exactly ~N~ characters, where ~N~ is an even number. Exactly half of those characters is equal to the open parenthesis ((), while the other half is equal to the closing parenthesis ()). Additionally, instead of the usual "forgot your password?" functionality, their engineers have decided to expose an API to the forgetful administrator. Using the API, an administrator can execute at most ~Q~ queries asking "whether the interval of the password from ~a~-th to the ~b~-th character is mathematically valid".

The mathematical validity of a sequence of parentheses is defined inductively as:

• ~()~ is a mathematically valid sequence.
• If ~A~ is a mathematically valid sequence, then ~(A)~ is a mathematically valid sequence as well.
• If both ~A~ and ~B~ are mathematically valid sequences, then ~AB~ is also mathematically valid.

Interaction

This is an interactive task. Your program must communicate with a program made by the organizers which simulates the functionality of a fictitious insecure CIA server from the task description.

Before interaction, your program should read an even integer ~N~ and an integer ~Q~ from the standard input. The meaning of both numbers is described in the task statement.

After that, your program can send query requests by writing to the standard output. Each query must be printed in a separate line and have the form ? a b, where ~1 \le a \le b \le N~ holds. After each query has been written, your program should flush the output and read the answer from the standard input. The answer is a ~1~ if the interval of the password starting from ~a~-th and ending at the ~b~-th character forms a mathematically valid sequence of parentheses. Otherwise, the answer is ~0~. Your program can make at most ~Q~ such queries.

After your program has deduced the secret password, it should write a line to the standard output in the form ! x1 x2 ... xN, where characters ~x_1, x_2, \dots, x_N~ represent the characters of the secret password. After that, your program should flush the output once more and gracefully terminate its execution.

Note: You can download the sample source code from the judging system that correctly interacts with the CIA server, including the output flush.

Constraints

Subtask	Points	Constraints
1	14	~1 \le N \le 1\,000, Q = \frac{N^2}{4}~, the whole password is a mathematically valid sequence.
2	7	~1 \le N \le 1\,000, Q = \frac{N^2}{4}~
3	57	~1 \le N \le 100\,000, Q = N-1~, the whole password is a mathematically valid sequence.
4	22	~1 \le N \le 100\,000, Q = N-1~

Sample Interaction

>>> denotes your output. Do not print this out.

The sequence is ((())).

6 9
>>> ? 1 6
1
>>> ? 1 2
0
>>> ? 2 4
0
>>> ? 2 5
1
>>> ? 3 4
1
>>> ! ((()))

Explanation for Sample Interaction

The secret password is ((())) of length ~6~, and a program may ask at most ~9~ queries.

For the first query, the whole password is mathematically valid.

For the second query, (( isn't mathematically valid.

For the third query, (() isn't mathematically valid.

For the fourth query, (()) is mathematically valid.

For the fifth query, () is mathematically valid.

The answer matches the password, and the CIA is compromised.