AT_arc070_d.[ARC070F] HonestOrUnkind

problemUrl

这是一道交互式问题。

鹿 AtCoDeer 君发现有 $N$ 个人聚集在一起，每个人的编号分别为 $0$ 到 $N-1$。其中有 $A$ 个人是诚实者，剩下的 $B(=N-A)$ 人是不诚实者。这 $N$ 个人都清楚每个人究竟是诚实者还是不诚实者。而 AtCoDeer 君只知道有 $A$ 个诚实者和 $B$ 个不诚实者，其余信息一无所知。于是，他打算通过对这 $N$ 个人提问，从而确定所有诚实者的编号。

每次提问，AtCoDeer 君可以选择两个整数 $a$ 和 $b$（$0 \leq a, b \leq N-1$），并向编号为 $a$ 的人提问：“编号为 $b$ 的人是诚实者吗？”

诚实者总是会对问题给出 Yes 或 No 的正确回答。而不诚实者则会任意地选择 Yes 或 No 回答。也就是说，他们既可能总说谎，也可能随机作答，甚至可能采用其他非简单的欺骗策略。

AtCoDeer 君最多可以进行 $2\times N$ 次提问。提问过程是顺序进行的，可以根据之前得到的结果来决定后续的问题。

请你确定所有诚实者的身份。如果无法做到（更准确地说，即使不管怎么问 $2\times N$ 次，不诚实者总能通过一种回答策略使得诚实者集合的可能情况大于等于 $2$ 种），请输出相应的信息。

首先，标准输入会给出 $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。

无特定输出格式要求，交互内容已在输入格式中给出。

数据范围

• $1 \leq A, B \leq 2000$

评测说明

• 每次输出后，必须刷新标准输出。 否则可能出现 TLE。
• 输出最终答案后，必须立即终止程序，未按要求终止程序的行为未定义。
• 如果输出的答案错误，评测器的行为未定义（不一定是 WA）。

样例解释 #1

此样例中，$A = 2$，$B = 1$，答案是 101。

样例解释 #2

此样例中，$A = 1$，$B = 2$，答案为 Impossible。