問題文

この問題はインタラクティブな問題です。

kaage 君と penguinman 君は NG ワードゲームで遊んでいます。 このゲームは次のように進行します。

• penguinman 君が NG ワードとして、 0 または 1 で構成される長さ N の文字列を 1 つ決める。
• kaage 君が次のような質問を繰り返す。
  • 0 または 1 で構成される長さ 1 以上 3000 以下の文字列 S を 1 つ決める
  • NG ワードが S の部分列であるかを質問する
• 2000 回以下の質問で NG ワードを特定できたら kaage 君の勝ち、特定できなかったら penguinman 君の勝ちとなる。

kaage 君は忙しいので、代わりに NG ワードを特定するプログラムを書いてください。

ただし、文字列 X が文字列 Y の部分列であるとは、 Y の文字を 0 文字以上取り除き、残った文字を元の順番で並べた物が X となることを言います。

制約

• 1 \leq N \leq 1000
• N は整数

入出力

最初に、 N が以下の形式で与えられる。

N

次に、質問を繰り返し送る。この回数は 2000 回以下でなければならない。
質問する文字列を S として、質問は以下の形式で出力せよ。ただし、 S は 0 または 1 で構成される長さ 1 以上 3000 以下の文字列である必要がある。

? S

これに対する返答は、 Yes または No である。これは、 NG ワードが S の部分列であるかを表している。

NG ワードを答えるときは、その文字列を NG として、以下の形式で出力せよ。

! NG

NG ワードの出力は質問の回数に含まれないことに注意せよ。

なお、 2000 回以下の質問で NG ワードを特定できることは証明できる。

注意

• 出力した後に、出力を flush する必要がある。そうしない場合、 TLE する可能性がある。
• NG ワードを答えた後プログラムを終了させなかった場合、ジャッジ結果は不定である。
• 正しくない形式で出力をしたり、 2000 回より多くの質問をした場合は、ジャッジ結果は不定である。

入出力例

この入出力例では、 N=3 であり、 NG ワードは 110 であるときのジャッジとのやり取りの一例を示しています。
なお、これはあくまで入出力例であり、意味のあるやりとりをしているとは限らないことに注意してください。

原案: kaage