Interactive Password Recovery

The CIA server's main password consists of \( n \) characters (with \( n \) being even) in which exactly \( \frac{n}{2} \) are left parentheses and \( \frac{n}{2} \) are right parentheses. Some forgetful administrators might lose the password, so the server provides a tool to recover it. An administrator may use this tool at most \( Q \) times. Each time the tool is used, it queries whether the substring from position \( l \) to \( r \) forms a valid parentheses sequence.

A valid parentheses sequence is defined as follows:

• \( () \) is valid.
• If \( A \) is valid, then \( (A) \) is also valid.
• If both \( A \) and \( B \) are valid, then the concatenation \( AB \) is also valid.

Your task is to simulate the administrator's process of finding the main password. Before any interactive queries, your program should first read two integers \( n \) and \( Q \) from input. Then, your program may send queries in the form ? a b (with \( 1 \leq a \leq b \leq n \)). After you have deduced the password, output it in the form ! x1 x2 ... xn and terminate the program.

Note: For the purpose of this problem, you can assume that the complete password is provided as input on the second line. Hence, you do not actually need to perform interactive queries; you may simply output the provided password.

inputFormat

The first line contains two integers ( n ) and ( Q ). The second line contains a string of ( n ) characters, which is the main password composed of '(' and ')'.

outputFormat

Output a single line starting with an exclamation mark followed by a space and the recovered password. For example: ! (())()

sample

4 3
()()

! ()()