KUPC-kunは、以下の問題を解くプログラムを作成しました。

$N$ 頂点を持つ木 $T = (V, E)$ が与えられます。 長さ $k$ の頂点列 $\{a_1, \dots, a_k\}$ に対して、そのスコアを以下のように定義します。

• $d(u, v)$ を木 $T$ における頂点 $u$ と $v$ の間のパスの辺の数とします。このとき、スコアは $\prod_{i=1}^{k} d(a_i, a_{(i \bmod k)+1})$ です。

$V$ の部分集合 $S$ が与えられます。各 $1 \le k \le N$ について、以下の値 $q_k$ を求めてください。

• 要素が $S$ に属する長さ $k$ のすべての頂点列 $\{a_1, \dots, a_k\}$ についてのスコアの総和。ただし、$2^{61} - 1$ を法とします。

KUPC-kunは木 $T$ の情報をあらかじめ秘密裏に保持しており、プログラムに与えられる木として $T$ を使用し続けます。

あなたは、上記のプログラムを使用して、木 $T$ の葉の情報を復元しようとしています。木の頂点数を $N$ とするとき、以下の質問を最大 $N$ 回まで行うことができます。

• $V$ の部分集合 $S$ を選び、プログラムの出力を問い合わせる。

KUPC-kunのプログラムが正しいと仮定して、質問を通じて得られた情報から木 $T$ に含まれるすべての葉を特定してください。 ジャッジは適応的ではなく、木 $T$ はインタラクション開始前に固定されています。

インタラクション

まず、標準入力から $N$ が与えられます。$(2 \le N \le 50)$

各質問について、以下の形式で標準出力に出力してください。

? s1s2 · · · sN

ここで、$s_1s_2 \dots s_N$ は部分集合 $S$ を表す長さ $N$ の文字列であり、$i \in S$ ならば $s_i = 1$、$i \notin S$ ならば $s_i = 0$ です。

これに対する応答として、標準入力から以下が与えられます。

q1 q2 · · · qN

すべての葉を特定したら、以下の形式で回答を出力してください。

! t1t2 · · · tN

ここで、$t_1t_2 \dots t_N$ は長さ $N$ の文字列であり、$i$ が葉ならば $t_i = 1$、葉でないならば $t_i = 0$ です。

この出力の後、直ちにプログラムを終了してください。

何かを出力するたびに、末尾に改行を出力し、標準出力をフラッシュしてください。

入出力例

入力 1

5
0 8 0 32 0
0 44 108 968 3960
0 0 0 0 0
0 76 348 3336 22200

出力 1

? 00101
? 11001
? 10000
? 11111
! 11001

注記

最初の例において、ジャッジが秘密裏に保持している木の辺集合は $(1, 3), (2, 3), (3, 4), (4, 5)$ です。 最初の質問では、$S = \{3, 5\}$ です。 $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$ であることに注意してください。

例えば、要素が $S$ に属する長さ 2 の頂点列 $a$ は以下の 4 通りあります。

• $a = (3, 3)$ のとき、この列のスコアは $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• $a = (3, 5)$ のとき、この列のスコアは $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• $a = (5, 3)$ のとき、この列のスコアは $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• $a = (5, 5)$ のとき、この列のスコアは $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

ジャッジは $q_2$ に対して $8$ を返します。これは $0 + 4 + 4 + 0$ を $2^{61} - 1$ で割った余りです。 他の列の長さについても同様に計算することで、ジャッジの応答 0 8 0 32 0 が得られます。 この木の葉は頂点 1, 2, 5 であり、! 11001 と出力することで葉の特定が正しく完了します。