Background

Statement

There is a hidden valid bracket string $S$ in the system, consisting only of ( and ).

Each time, you may ask the system about a subsegment $S[l,r]$ of $S$, and the system will return whether this subsegment is a valid bracket string.

Write a program to interact with the system and finally output the exact information of $S$.

Definition of a valid bracket string:

• The empty string is a valid bracket string.

• Let $\text{A}$ be a valid bracket string, then $\text{(A)}$ is also a valid bracket string.

• Let $\text{A}$ and $\text{B}$ be valid bracket strings, then $\text{AB}$ is also a valid bracket string.

Interaction Process

You can write a function getProgram() and include grader.h at the beginning of the program to complete the interaction process. This function has no return value and no parameters.
Please write a complete program directly to complete the interaction.

You first need to read an integer $n$ from standard input, which is the length of the system string.

You can output queries and the final answer to standard output in the following form:

• To query whether a substring is valid, you should first output a character ?, followed by two integers $l,r$, meaning you choose $S[l,r]$. Separate the character and integers with a single space. If $S[l,r]$ is a valid bracket string, the interactive library will output $\texttt{Yes}$ to standard output; otherwise it will output $\texttt{No}$.

• To output the final answer, you should first output a character !, followed by a valid bracket string of length $n$. Separate ! and the string with a single space.

After answering, you should terminate the program. It is guaranteed that the quadcopter program will not change during the interaction.

During the interaction, your number of queries must not exceed a value $k$.

Hint

Constraints

Translated by ChatGPT 5