Students are preparing to participate in a quadcopter programming competition. The quadcopter used in the competition can perform two commands: move up by 1 meter and move down by 1 meter. The "up" command is denoted by the symbol '(', and the "down" command is denoted by the symbol ')'.

A program for the quadcopter is a sequence of commands. A program is considered correct if, starting from ground level and executing all commands in sequence, the quadcopter returns to ground level. Furthermore, during the execution of the program, the quadcopter must not attempt to go below ground level.

For example, the following programs are correct: "()(())", "((()))". The program "(((" is not correct because the quadcopter finishes at a height of 3 meters above ground level. The program "())( " is also not correct because, upon executing the third command, the quadcopter attempts to go below ground level.

A contestant has written a correct program for the quadcopter consisting of $n$ commands, numbered from 1 to $n$. They loaded it into the quadcopter's memory for a demonstration during the competition. Unfortunately, after loading the program, the contestant accidentally deleted it from their computer, and the quadcopter does not allow the program to be downloaded from its memory.

Fortunately, the quadcopter supports a special debugging mode. In this mode, the quadcopter with the loaded program can respond to special queries. Each query consists of two integers: $l$ and $r$, where $1 \le l \le r \le n$. In response to a query, the quadcopter reports whether the fragment of the loaded program consisting of commands from the $l$-th to the $r$-th inclusive is a correct program for the quadcopter. The contestant wants to use the debugging mode to recover the program loaded in the quadcopter.

You are required to write a solution program that interacts with the jury's program, which simulates the quadcopter's debugging mode, and ultimately recovers the program loaded in the quadcopter.

Interaction

This is an interactive problem.

First, an integer $n$ is provided as input — the number of commands in the quadcopter program ($2 \le n \le 50\,000$).

For each test case, the jury has fixed a number $k$ — the maximum number of queries. It is guaranteed that $k$ queries are sufficient to solve the problem. This number is not provided to the solution program. The constraints on $k$ for different subtasks are given in the scoring table. If the solution program makes more than $k$ queries to the jury's program, it will receive a "Wrong Answer" verdict for that test case.

To make a query, the solution program must output a string in the format "? $l$ $r$", where $l$ and $r$ are positive integers specifying the fragment of the quadcopter program ($1 \le l \le r \le n$).

In response to the query, the jury's program provides as input either the string "Yes" or the string "No", depending on whether the requested fragment of the quadcopter program is a correct program.

If the solution program has determined the answer to the problem, it must output the string "! $c_1c_2 \dots c_n$", where the symbol $c_i$ specifies the $i$-th command in the quadcopter program and is either '(' or ')'.

After this, the solution program must terminate.

It is guaranteed that in each test case, the program in the quadcopter's memory is a fixed correct program that does not change based on the queries made by the solution program.

Examples

Input 1

4
Yes
No
Yes
Yes

Output 1

? 1 4
? 1 3
? 1 2
? 3 4
! ()()

Input 2

6
Yes
No
Yes

Output 2

? 3 4
? 1 2
? 2 5
! ((()))

Note

The provided examples illustrate the interaction between the solution program and the jury's program "step-by-step". In the first example, $n=4$. The only possible correct program of two commands is "()", so from the results of the third and fourth queries, one can conclude that the program in the quadcopter's memory is "()()". Therefore, in particular, the answer to the second query is indeed "No", as the program fragment "()(" is not a correct program: if the quadcopter executes these three commands, it will remain at a height of one meter above the ground.

In the second example, $n=6$, and the queries made are sufficient to uniquely determine that the program in the quadcopter's memory is "((()))".

In the test cases from the problem statement, $k=150$, meaning that no more than 150 queries are allowed.

Subtasks