この問題はインタラクティブ問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
KUPC君は以下の問題を解くプログラムを作成しました。
| \(N\) 頂点の木 \(T=(V,E)\) が与えられます。 \(T\) の頂点からなる長さ \(k\) の列 \(\{a_1,\ldots,a_{k}\}\) に対するスコアを以下のように定義します。
\(V\) の部分集合 \(S\) が与えられるので、各 \(1 \leq k \leq N\) について以下の値 \(q_k\) を求めてください。
|
KUPC君は予め木 \(T\) の情報を隠し持っており、プログラムに入力する木として \(T\) を使い続けます。
あなたは上のプログラムを用いて葉の情報を復元しようとしています。木の頂点数を \(N\) として、以下の質問を高々 \(N\) 回行うことができます。
KUPC君のプログラムが正しいと仮定して、質問の情報から木 \(T\) に含まれる葉を全て特定してください。
なお、ジャッジは適応的 (adaptive) ではなく、木 \(T\) はやりとりの前から固定されています。
最初に \(N\) が標準入力で与えられます。(\(2 \leq N \leq 50\))
質問は、以下の形式で標準出力に出力してください。
| ? \(s_1s_2\cdots s_N\) |
ここで、\(s_1s_2\cdots s_N\) は部分集合 \(S\) を表す長さ \(N\) の文字列で、\(i \in S\) ならば \(s_i=1\) 、\(i \notin S\) ならば \(s_i=0\) としてください。
これに対する応答は、次の形式で標準入力から与えられます。
| \(q_1\) \(q_2\) \(\cdots\) \(q_N\) |
全ての葉が特定できたら、解答を以下の形式で出力してください。
| ! \(t_1t_2\cdots t_N\) |
ここで、\(t_1t_2\cdots t_N\) は長さ \(N\) の文字列で、\(i\) が葉ならば \(t_i=1\) 、葉でないならば \(t_i=0\) としてください。
この出力の後、ただちにプログラムを終了してください。
出力を行うたびに、末尾に改行を入れて標準出力を flush してください。
5 0 8 0 32 0 0 44 108 968 3960 0 0 0 0 0 0 76 348 3336 22200
? 00101 ? 11001 ? 10000 ? 11111 ! 11001
\(1\) つ目のサンプルについて、ジャッジが隠し持っている木の辺集合は \((1,3),(2,3),(3,4),(4,5)\) です。
\(1\) つ目の質問について、 \(S=\{3,5\}\) です。
\(d(3,3)=0,d(3,5)=d(5,3)=2,d(5,5)=0\) に留意してください。
例えば、 \(S\) の要素からなる長さ \(2\) の頂点列 \(a\) は以下の \(4\) 通りです。
ジャッジは \(q_2\) として \(0+4+4+0\) を \(2^{61}-1\) で割ったあまりである \(8\) を応答します。
他の列の長さについても同様に計算することで、ジャッジの応答 0 8 0 32 0 を得ます。
この木の葉は頂点 \(1,2,5\) であり、 ! 11001 と出力することで葉の特定が正しく完了します。