前言：本文不含信竞内容，请放心食用喵。

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

输入 #1

2 1

N

Y

Y

Y

Y

输出 #1

? 0 1

? 0 2

? 1 0

? 2 0

? 2 2

! 101

输入输出样例 #2

输入 #2

1 2

输出 #2

Impossible

说明/提示

数据范围

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

评测说明

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

样例解释 #1

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

样例解释 #2

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

猫猫喜欢你们喵猫猫教你切黑题喵。

我们称诚实者为好人喵，不诚实者为坏人喵。

容易发现，此题可先通过 $N$ 次询问确定一个好人，然后依次询问其他人，恰好 $2*N$ 次喵。

看到这种题，先考虑无解的情况，手玩一些小数据（小小的也很可爱喵），譬如 $A=B=2$ 时，经过一些尝试，可以发现是无解的喵。

我们猜测 $A\le B$ 时，是无解的，猫猫脑子不太好使喵，证明就留给读者吧喵。

骗你的，其实有证明（好玩喵）：

坏人可以构造一个包含 $a$ 个坏人的小团体，这些人声称小团体里是好人，外是坏人，这样是无法判断的喵（坏蛋喵）。

我们不妨钦定其他情况一定有解，此时 $a>b$，这里一定要跳脱特解的思维定式，不应被束缚（束缚喵），大家可以思考一下喵。

（猫娘部分结束）

我们考虑维护一个栈（栈：每次从顶部进出），使得其上面是好人，下面是坏人，依次枚举每个人，每次若栈为空，直接插入，否则向栈顶询问此人的好坏，依结果分讨。

1. 若回答为 Yes，再进行分讨，若栈顶为好人，此人也为好人，否则，栈里没有好人，无论如何，将此人插入栈都不破坏性质。

2. 若好的为 No，此时没有很好的方法区分，但是，此时这二人中必有至少一个坏人，我们直接将栈顶踢出（且此人不入栈）。这样，性质显然不会被破坏。

由于操作中好人数量始终大于坏人，据性质，最后栈顶一定是好人，这样，我们就通过至多 $N$ 次询问找到了一个好人！

于是，目标达成。

实现？ 被猫猫吃了喵。