AT_agc072_d.[AGC072D] Magician

这是一个交互式问题。

桌面上有 $\binom{2N}{N}$ 张卡片，编号为 $1$ 到 $\binom{2N}{N}$。第 $i$ 张卡片的正面印有由 $N$ 个 0 和 $N$ 个 1 组成的、按字典序第 $i$ 小的长度为 $2N$ 的字符串，共有 $\binom{2N}{N}$ 种不同的字符串。

具体例子：例如当 $N=2$ 时，卡片 $1, 2, 3, 4, 5, 6$ 的正面分别印有 0011、0101、0110、1001、1010、1100。

魔女 Alice 会在每张卡片的背面写上前 $N$ 个大写英文字母中的某一个（例如 $N=2$ 时为 A、B），然后进行如下的 魔法 操作共 $T$ 次。

一次魔法的流程

1. 主持人宣布前 $N$ 个大写英文字母中的某一个字母 $s$。
2. 主持人在黑板上写下一个全为 0 的长度为 $2N$ 的字符串。
3. 依次进行 $i=1,2,\dots,N$ 的如下操作。这里 $a_1, b_1, \dots, a_N, b_N$ 是 $1$ 到 $2N$ 之间互不相同的整数。
   • 首先，主持人将整数 $a_i$ 和 $b_i$ 告诉 Alice。
   • 然后，Alice 需要将黑板字符串的第 $a_i$ 或第 $b_i$ 个字符中的一个改为 1（只能改一个）。
4. 此时黑板上的字符串为 $x$。正面印有 $x$ 的卡片恰好有一张，查看其背面。如果背面的字母是 $s$，则本次魔法成功，否则失败。

注意，Alice 在决定将 $a_i$ 或 $b_i$ 位置改为 1 之前，并不知道后续 $a_{i+1}, b_{i+1}$ 的信息。

请实现一种策略，使得 $T$ 次魔法全部成功。现在，开始吧。

首先，从标准输入读取两个整数 $N, T$，格式如下：

$N$ $T$

接下来，输出每张卡片背面要写的字母 $c_i$，格式如下，末尾需换行。这里 $c_i$ 必须是前 $N$ 个大写英文字母之一。

$c_1\ c_2\ \cdots\ c_{{}_{2N}\mathrm{C}_N}$

然后，以下过程重复 $T$ 次。第 $t$ 次（$1 \leq t \leq T$）对应第 $t$ 次魔法。

首先，从标准输入读取主持人宣布的字母 $s$，格式如下：

$s$

接着，依次进行 $i=1,2,\dots,N$ 的如下操作。

• 首先，输入两个整数 $a_i, b_i$，格式如下：

$a_i$ $b_i$

• 然后，输出要改为 1 的位置 $d$，格式如下。$d$ 必须为 $a_i$ 或 $b_i$ 之一，末尾需换行。

$d$

如果输出格式有误，或上一次魔法失败，之后不会再输入 $s$ 或 $(a_i, b_i)$，而是输入 $-1$。此时应立即终止程序。（如果是在第 $T$ 次魔法首次失败，或第 $T$ 次魔法的 $i=N$ 时首次输出格式有误，则之后不会再有任何输入）

见上文输入格式说明。

限制条件

• $2 \leq N \leq 10$
• $1 \leq T \leq 5\,000$
• $s$ 是前 $N$ 个大写英文字母之一
• $1 \leq a_i < b_i \leq 2N$
• $a_1, b_1, a_2, b_2, \dots, a_N, b_N$ 互不相同
• $a_1, b_1, a_2, b_2, \dots, a_N, b_N, s$ 在与评测机交互前已确定
• $N, T, a_i, b_i$ 均为整数

注意事项

每次输出后都要刷新输出流。 否则可能会因未及时输出而被判定为 TLE。

此外，如果从输入读到 -1，应立即终止程序。此时评测结果为 WA，但如果不终止，评测结果将不可预期。请注意，额外的换行也可能被视为输出格式错误。

本题的评测系统是非自适应的（non-adaptive）。即 $a_1, b_1, a_2, b_2, \dots, a_N, b_N, s$ 的值在与评测机交互前已确定，不会因你的输出而改变。

输入输出样例

以下示例仅为交互过程的一个例子。

输入	输出	说明
2 2		首先输入整数 $N$ 和 $T$。
	ABABAB	输出 $6$ 张卡片背面的字母。
A		第 $1$ 次魔法开始。主持人宣布字母 A。
1 2		$(a_1, b_1) = (1, 2)$。
	2	将第 $2$ 位改为 1。
3 4		$(a_2, b_2) = (3, 4)$。
	3	将第 $3$ 位改为 1。最终黑板字符串为 0110，正面为 0110 的卡片背面是 A，魔法成功。
B		第 $2$ 次魔法开始。主持人宣布字母 B。
1 3		$(a_1, b_1) = (1, 3)$。
	1	将第 $1$ 位改为 1。
2 4		$(a_2, b_2) = (2, 4)$。
	2	将第 $2$ 位改为 1。最终黑板字符串为 1100，正面为 1100 的卡片背面是 B，魔法成功。

由 ChatGPT 4.1 翻译