题目描述

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

シカのAtCoDeerくんは $0$~$N-1$ の番号がついた $N$ 人の人が集まっているのを見つけました。 この内 $A$ 人は正直者で、残りの $B(=N-A)$ 人は不親切な人です。 $N$ 人の人は全員、誰が正直者で、誰が不親切な人かを把握しています。 一方、AtCoDeerくんは、正直者が $A$ 人いて不親切な人が $B$ 人いることしか知りません。 そこで、AtCoDeerくんはこれらの $N$ 人に質問をして、正直者を全員特定しようとしています。 一回の質問では、AtCoDeerくんは、$0≦a,b≦N-1$ なる $a$, $b$ を選んで、$a$ さんに「$b$ さんは正直者ですか?」という質問をします。

正直者は、質問に対し常に Yes か No の正しい答えを返します。 一方、不親切な人は、質問に対し Yes か No のどちらかを恣意的に選んで返します。 つまり、常に嘘をついたり、半分の確率でランダムに答えるといった単純なアルゴリズムではない可能性があります。

AtCoDeerくんは高々 $2N$ 回質問をすることができます。質問は順番に行われ、以前の質問の結果から次の質問を決めることが出来ます。

正直者を全員特定してください。 不可能な場合(正確には、どのような $2N$ 回の質問をしようと、不親切な人たちがうまく返答することで、正直者の集合としてありうるものが2つ以上存在するようにできる場合)は、その旨を出力してください。

Input & Output Format

最初に、標準入力から $A$ と $B$ が以下の形式で与えられる:

$A$ $B$

もし特定が不可能な場合は、即座に次のように出力し、プログラムを終了しなければならない。:

Impossible

それ以外の場合は、次に、クエリを質問する。 各クエリは、標準出力に以下の形式で出力されなければならない:

? $a$ $b$

ここで $a$ と $b$ は $0$ 以上 $N-1$ 以下の整数でなければならない。

次に、クエリの答えが標準入力から以下の形式で与えられる:

$ans$

ここで $ans$ は Y または N である。 Y のときは質問の答えが Yes であることを、N のときは No であることを表す。

最後に、答えを以下の形式で出力しなければならない：

! $s_0s_1...s_{N-1}$

ここで $s_i$ は $i$ 番の人が正直者なら 1、不親切な人なら 0 でなければならない。

题目大意

现在有 $n$ 个人，编号从 $0\sim n-1$。这些人中有 $a$ 个人是诚实的，剩下的 $b$ 个人是不友好的。这 $n$ 个人都知道各自的身份，但是你只知道有 $a$ 个诚实的人和 $b$ 个不友好的人，你现在试图通过询问来得知他们的身份。

你可以进行询问，询问格式类似于 ? x y，表示向 $x$ 询问 $y$ 是否是诚实的。返回答案按照如下规则：

• 如果 $x$ 是诚实的人，那么他会按照事实返回答案，也就是说如果 $y$ 是诚实的，返回答案就为 $\rm Y$，否则返回 $\rm N$。
• 如果$x$是不友好的人，那么他会任意选择 $\rm Y$ 和 $\rm N$ 来回答。也就是说 $x$ 是可以按照某种策略来回答你的问题的。

现在请你在 $2n$ 次询问以内确定 $n$ 个人的身份，如果不可能，请输出 Impossible，否则请按照 ! S0S1S2...Sn-1 的格式输出（其中 $0,1,2,\ldots,n-1$ 都为下标，$S_i$ 表示 $i$ 的身份，如果第 $i$ 个人是诚实的，请输出 $1$，否则输出 $0$，身份之间没有空格）。

如下是一个成功的询问的示例：

void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}

上面这个交互函数中的 $s$ 为字符串变量，用来读入返回的答案。

提示

制約

• $1≦A,B≦2000$

ジャッジ

• 出力のあと、標準出力を flush しなければならない。 そうでないときは TLE の可能性がある。
• 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
• 出力の答えが間違っている場合の挙動は定義されていない (WAとは限らない)。

サンプル

このサンプルでは $A\ =\ 2$, $B\ =\ 1$ で、答えは 101 である。

Input Output $2$ $1$ $?$ $0$ $1$ $N$ $?$ $0$ $2$ $Y$ $?$ $1$ $0$ $Y$ $?$ $2$ $0$ $Y$ $?$ $2$ $2$ $Y$ $!$ $101$次のサンプルでは $A\ =\ 1$, $B\ =\ 2$ で、答えは Impossible である。

Input Output $1$ $2$ $Impossible$