Background

Yvonne and Chen Qianyu are playing a game.

Problem

Chen Qianyu has $N$ depot loaders in front of her, numbered $0$ to $N-1$ from left to right. Each depot loader can be set to output one of two minerals: Originium Ore or Ferrium Ore. The depot loaders are connected to a tansport belt system that shuffles the outputs from the depot loaders in a fixed order and delivers them to $N$ output ports, but Chen Qianyu does not know this order. The output ports are numbered $0$ to $N-1$ from left to right. In front of each output port stands a "Flashfreezer".

Yvonne will have the Flashfreezers report numbers from left to right, following these rules:

• The leftmost Flashfreezer reports $0$.
• For each subsequent Flashfreezer, if the mineral in front of him is different from the mineral in front of the Flashfreezer immediately to his left, he reports the number reported by the left neighbor plus $1$; otherwise, he reports the same number as the left neighbor.

Then, Yvonne tells Chen Qianyu the number reported by the last Flashfreezer.

Chen Qianyu can conduct multiple experiments: each time, she can freely set the mineral types for all input ports, and then she receives the last Flashfreezer's reported number. Her goal is to determine which two depot loaders correspond to the two endpoint output ports (output port $0$ and output port $N-1$).

Since Chen Qianyu is exceptionally intelligent, she has called upon you, the Endministrator, to help her win the game.

Interaction

• Your program should first read a line containing an integer $N$: the number of depot loaders.
• Then, your program should interact with the interactor. To start an experiment, you should output a line starting with a question mark ?, followed by a string of length $N$ consisting of $0$ (for Originium Ore) and $1$ (for Ferrium Ore), indicating how you set the outputs of the $N$ depot loaders. After that, your program should read an integer $l$ $(0 \leq l < N)$, which is the number reported by the last Flashfreezer.
• When you are ready to answer, output a line starting with an exclamation mark !, followed by two integers $A$ and $B$ $(0\leq A,B < N)$. For your answer to be accepted, these must be the depot loader numbers corresponding to output port $0$ and output port $N-1$, in any order. After this, your program should exit.

The interactor is non-adaptive, meaning the mapping between depot loaders and output ports is fixed before the interaction starts.

Make sure to flush the standard output after each experiment; otherwise, your program might be judged as Time Limit Exceeded. In Python, using input() to read lines automatically flushes output. In C++, cout << endl; flushes the output in addition to printing a newline; if you use printf, use fflush(stdout).

Example 1

Hidden mapping:

In Example 1, there are $5$ depot loaders. In the first experiment, the minerals in front of the Flashfreezers (from left to right) are Originium Ore, Originium Ore, Ferrium Ore, Originium Ore, Ferrium Ore, and their reported numbers are $[0, 0, 1, 2, 3]$, so the interactor outputs $3$. In the second experiment, the minerals are Ferrium Ore, Originium Ore, Ferrium Ore, Ferrium Ore, Originium Ore, and their reported numbers are $[0, 1, 2, 2, 3]$, so the interactor outputs $3$. Finally, Chen Qianyu concludes that the depot loaders corresponding to output port $0$ and output port $N-1$ are the $2$nd and $4$th depot loaders (order irrelevant). Both ! 2 4 and ! 4 2 are acceptable answers.

Example 2

Hidden mapping:

In Example 2, there are $3$ depot loaders. In the first experiment, the minerals are Ferrium Ore, Ferrium Ore, Ferrium Ore, and the reported numbers are $[0, 0, 0]$, so the interactor outputs $0$. In the second experiment, the minerals are Ferrium Ore, Originium Ore, Ferrium Ore, and the reported numbers are $[0, 1, 2]$, so the interactor outputs $2$. In the third experiment, the minerals are Originium Ore, Originium Ore, Originium Ore, and the reported numbers are $[0, 0, 0]$, so the interactor outputs $0$. Finally, Chen Qianyu concludes that the depot loaders corresponding to output port $0$ and output port $N-1$ are the $0$th and $1$st depot loaders (order irrelevant). Both ! 0 1 and ! 1 0 are acceptable answers.

Example 3

Hidden mapping:

In Example 3, there are $4$ depot loaders. In the first experiment, the minerals are Ferrium Ore, Originium Ore, Ferrium Ore, Originium Ore, and their reported numbers are $[0, 1, 2, 3]$, so the interactor outputs $3$. Finally, Chen Qianyu concludes that the depot loaders corresponding to output port $0$ and output port $N-1$ are the $0$th and $3$rd depot loaders (order irrelevant). Both ! 0 3 and ! 3 0 are acceptable answers.

Constraints and Notes

For all input data, it holds that:

• $3 \leq N \leq 30000$
• You can initiate at most $30$ experiments (outputting the final answer does not count towards this limit). If you exceed this limit, your submission will be judged as "Wrong Answer".

Detailed subtask constraints and scores are shown in the table below.