20051번 - Zagrade 서브태스크다국어인터랙티브

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.

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 ≤ a ≤ b ≤ 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 “! x1x2...xN”, where characters x₁, x₂, . . . , 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 interact with the CIA server, including the output flush.