Description

Go 语言的设计目标是提供简单的 API 并支持多线程。Code Jam 团队希望将这些目标发挥到极致，因此我们提出了一种新语言，名为 Go++。

Go++ 语言只使用一个寄存器，该寄存器存储一个布尔值（0 或 1）。寄存器初始值为 0。该语言有三种指令：

• $\mathbf{0}$，将寄存器设置为 0。
• $\mathbf{1}$，将寄存器设置为 1。
• $\mathbf{?}$，输出当前寄存器的值。

很简单，对吧？为了支持多线程，我们允许两段不同的 Go++ 程序同时运行，并共享同一个寄存器。每条指令都是原子的——也就是说，每条指令必须完全执行完毕后，下一条指令才能开始执行。不过，两段程序的指令可以以任意方式交错执行，只要每段程序内部指令的相对顺序不变。

例如，下面是将两段程序 $1\mathbf{?}$ 和 $\mathbf{?} \mathbf{0}$ 同时执行时所有可能的六种交错方式（下划线仅用于区分第二段程序的指令）：

• $\mathbf{?}\mathbf{0}1\mathbf{?}$，输出为 $\mathbf{0\ 1}$。（记住寄存器初始为 0。）
• $\mathbf{?}1\mathbf{0}\mathbf{?}$，输出为 $\mathbf{0\ 0}$。
• $\mathbf{?}1\mathbf{?}\mathbf{0}$，输出为 $\mathbf{0\ 1}$。
• $1\mathbf{?}\mathbf{0}\mathbf{?}$，输出为 $\mathbf{1\ 0}$。
• $1\mathbf{?}\mathbf{?}\mathbf{0}$，输出为 $\mathbf{1\ 1}$。
• $1\mathbf{?}\mathbf{?}\mathbf{0}$，输出为 $\mathbf{1\ 1}$。

注意，输出字符串始终只包含 $\mathbf{0}$ 和 $\mathbf{1}$，而不会有 $\mathbf{?}$，因为 $\mathbf{?}$ 不是寄存器的状态。

通常，程序员会写程序以产生期望的输出，而你的任务则是编写两段程序，保证不会产生某个“不良输出”！具体来说，你会得到一个长度为 $\mathbf{L}$ 的“不良字符串” $\mathbf{B}$，以及一个包含 $\mathbf{N}$ 个长度为 $\mathbf{L}$ 的“良好字符串”集合 $\mathbf{G}$。你需要构造两段 Go++ 程序（长度可以不同），使得两段程序以上述规则交错执行时，能够产生 $\mathbf{G}$ 中所有字符串，但绝不可能产生字符串 $\mathbf{B}$。如果还能产生其他既不是 $\mathbf{B}$ 也不在 $\mathbf{G}$ 的字符串，也没关系。注意，两段程序中 $\mathbf{?}$ 指令的总数必须恰好为 $\mathbf{L}$。两段程序总指令数不得超过 200。

举例来说，若 $\mathbf{B}=\mathbf{11}$，$\mathbf{G}=\{\mathbf{10}, \mathbf{00}\}$，则程序 $\mathbf{?}$ 和 $\mathbf{10?1}$ 是一个合法答案。它们能产生 $\mathbf{G}$ 中的所有字符串，但无论如何交错都不可能产生 $\mathbf{B}$。（它们也能产生 $\mathbf{01}$，但这既不是 $\mathbf{B}$ 也不在 $\mathbf{G}$，这没关系。）而程序 $1\mathbf{?}$ 和 $\mathbf{?}\mathbf{0}$ 不是合法答案，因为它们可能产生 $\mathbf{B}$。程序 $\mathbf{00}$ 和 $\mathbf{??}$ 也不是合法答案，因为它们无法产生 $\mathbf{G}$ 中的所有字符串。

你能否构造出满足条件的两段程序，或判断任务不可能完成（IMPOSSIBLE）？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组三行。每组的第一行为两个整数 $\mathbf{N}$ 和 $\mathbf{L}$，分别表示 $\mathbf{G}$ 中字符串数量，以及 $\mathbf{B}$ 和 $\mathbf{G}$ 中字符串的长度。第二行为 $\mathbf{N}$ 个长度为 $\mathbf{L}$ 的不同字符串，表示 $\mathbf{G}$。第三行为一个长度为 $\mathbf{L}$ 的字符串，表示不良字符串 $\mathbf{B}$。$\mathbf{B}$ 和 $\mathbf{G}$ 中所有字符串仅由 $\mathbf{0}$ 和 $\mathbf{1}$ 组成。

Output Format

对于每组测试用例，若无法满足条件，输出一行 Case #x: IMPOSSIBLE，否则输出一行 Case #x: y z，其中 $\mathbf{x}$ 为测试用例编号（从 1 开始），$\mathbf{y}$ 和 $\mathbf{z}$ 是你构造的两段程序。两段程序的总指令数不得超过 200，每段程序至少包含一条指令，且两段程序中 $\mathbf{?}$ 指令总数恰好为 $\mathbf{L}$。

3
2 2
10 00
11
3 2
11 10 00
01
4 2
00 01 10 11
11

Case #1: ? 10?1
Case #2: 1?? 0
Case #3: IMPOSSIBLE

Hint

样例解释

样例输出展示了一组可能答案，其他答案也可能是正确的。

样例第 1 组即为题面中的例子。

样例第 2 组不会出现在小数据集中。

样例第 3 组显然 IMPOSSIBLE，因为 $\mathbf{B}$ 就在 $\mathbf{G}$ 中。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{N} \leqslant 100$。
• $1 \leqslant \mathbf{L} \leqslant 50$。
• $\mathbf{G}$ 中所有字符串均不同。

小数据集（7 分，测试集 1 - 可见）

• $\mathbf{B}$ 全部由 $\mathbf{1}$ 组成。

大数据集（28 分，测试集 2 - 隐藏）

• $\mathbf{B}$ 可以是任意由 $\mathbf{0}$ 和/或 $\mathbf{1}$ 组成的字符串。

翻译由 GPT4.1 完成。