Contest Duration: - (local time) (200 minutes)
H - Huge Kingdom: Atcoder /

Time Limit: 4 sec / Memory Limit: 256 MB

Max Score: $1500$ Points

### Problem Statement

Huge kingdom: $Atcoder$ contains $N$ towns and $N-1$ roads. This kingdom is connected.

You have to detect the kingdom's road.
In order to detect, You can ask this form of questions.
• You can output a string $S$. Length of $S$ must be $N$ and The character of string $S$ must be represented by '$0$' or '$1$'.
• Computer paint the towns with white or black according to the character string you output.
• If $i$-th character of $S$ is '0', computer paint town $i$ white.
• If $i$-th character of $S$ is '1', computer paint town $i$ black.
• Please consider an undirected graph $G$.
• For each edge, computer do the following processing: If both ends painted black, computer adds this edge to $G$.
• Computer returns value $x$: sum of "diameter of tree"$^2$ about each connected components.
For example, when $S$="11001111" and the kingdom's structure is this, computer returns 10.
Please detect the structure of $Atcoder$ as few questions as possible.

### Input, Output

This is a reactive problem.
The first input is as follows:

$N$
• $N$ is number of towns in $Atcoder$.

Next, you can ask questions.
The question must be in the form as follows:
? $S$
$S$ is a string. The mean of $S$ written in the problem statement. Length of $S$ must be $N$.

The answer of question is as follows:
$x$
The mean of $x$ written in the problem statement.

Finally, your program must output as follows:
! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$
This output means your program detects all roads of $Atcoder$.
$(a_i,b_i)$ means there is a road between $a_i$ and $b_i$.

You can output roads any order, but you must output the answer on a single line.

### Constraints

• $N$=200
• $Atcoder$ contains $N-1$ roads and this kingdom is connected.
• All cases were made randomly.

### Scoring

Let the number of questions be $L$.

• If $L > 20000$, $score$ = $0$ points
• If $18000 < L ≦ 20000$, $score$ = $200$ points
• If $5000 < L ≦ 18000$, $score$ = $650-L/40$ points
• If $4000 < L ≦ 5000$, $score$ = $800-L/20$ points
• If $2000 < L ≦ 4000$, $score$ = $1400-L/5$ points
• If $1200 < L ≦ 2000$, $score$ = $1500-L/4$ points
• If $700 < L ≦ 1200$, $score$ = $1850-L/2$ points
• If $L ≦ 700$, $score$ = $1500$ points

There is $5$ cases, so points of each case is $score/5$.

### Sample Input

This case is $N=4$. This case is not include because this is not $N=200$.
N=4
0 1
1 2
1 3


### Sample Output

Sample interaction is as follows:
Input from computer Output
4
? 1111
4
? 1101
4
? 1001
0
? 1100
1
? 1011
0
! (0,1) (1,2) (1,3)

In this sample, structure of $Atcoder$ is as follows:

This question is not always meaningful.
この問題はマラソン問題です。 writer解が必ずしも満点であるとは限りません。できるだけ良い点数を取りましょう。

### 問題文

Atcoder王国は、$N$個の街と$N-1$個の道から成り立っています。
また、その王国は連結であります。つまり「木」です。

あなたは、その王国の構造を当てなければなりません。
ここでいう構造というのは、それぞれの道がどの番号の街とどの番号の街をつないでいるのか、という事です。

さて、あなたは構造を当てるにおいて、以下のような質問ができます。
• 文字列$S$($N$文字)を出力する。その時、$S_i$=1の時、$i$番目の街を黒く塗り、$S_i$=0の時、$i$番目の街を白く塗ることを意味する。
• $N$頂点のグラフ$G$を考える。
• 王国の道の両端の街が、両方とも黒く塗られている場合、グラフ$G$にその辺を追加する。
• グラフ$G$の各連結成分についての、「木の直径」を2乗した値の総和が返される。

その時、できるだけ少ない質問回数で王国の構造を当てなさい。

### 入出力

これはリアクティブ問題である。

$N$
• 1行に、Atcoder王国の街の個数$N$が与えられる。

? $S$
$S$は、質問する文字列（＝街の塗り方）である。$S$は$N$文字でなければならない。

また、質問は、以下のように返される。
$d$

グラフ$G$の各連結成分についての、「木の直径」を2乗した値の総和が返される。

! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$
それは、Atcoder王国の構造を突き止めたことを示す。
$(a_i,b_i)$は、街$a_i$と街$b_i$を直接つなぐ道があることを示す。

ただし、出力する道の順番はどのようなものでも良い。また、それぞれの道を出力する方法は2通りあるが、【(1,2),(2,1)など】その出力の順番もどれでもよい。

### 制約

• $N$ = $200$
• Atcoder王国には$N-1$本の道があり、連結である
• Atcoder王国の街の番号は$0$以上$N-1$以下である。(0-based)
• ケースはランダムに作られた。

### テストケースの生成方法

• ランダムな街の番号$u$, $v$を選ぶ。
• もし、今の状態で街$u$から街$v$まで、いくつかの道路を使ってたどり着けない場合、街$u$と$v$の間に道路を結ぶ。
• そうでない場合、何もしない。最初の操作に戻る。

### 得点

あなたが質問した回数を$L$とする。その時得点の理論値は以下のようになる。

• $L > 20000$の時、$0$点
• $18000 < L ≦ 20000$の時、$200$点
• $5000 < L ≦ 18000$の時、$650-L/40$点
• $4000 < L ≦ 5000$の時、$800-L/20$点
• $2000 < L ≦ 4000$の時、$1400-L/5$点
• $1200 < L ≦ 2000$の時、$1500-L/4$点
• $700 < L ≦ 1200$の時、$1850-L/2$点
• $L ≦ 700$の時、$1500$点

ケースは5個あるので、得点は理論値を$5$で割った値になる。

### 入力例

このケースは、$N=4$である。実際のケースではそのようなものは存在しない。（制約を満たしていないため）
N=4
0 1
1 2
1 3


### 出力例

プログラムへの入力 プログラムの出力
4
? 1111
4
? 1101
4
? 1001
0
? 1100
1
? 1011
0
! (0,1) (1,2) (1,3)

その王国は、以下の図のような構造をしています。

ただし, 必ずしも意味のある質問をしているとは限らない。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されます。