P13053 [GCJ 2020 #1A] Pattern Matching

许多终端使用星号(`*`)表示"任意字符串"，包括空字符串。例如，当列出匹配`BASH*`的文件时，终端可能显示 BASH、BASHER 和 BASHFUL。对于`*FUL`，可能显示 BEAUTIFUL、AWFUL 和 BASHFUL。当列出`B*L`时，可能显示 BASHFUL、BEAUTIFUL 和 BULL。 在本题中，**模式**是仅由大写字母和星号(`*`)组成的字符串，**名称**是仅由大写字母组成的字符串。若模式 $p$ 能通过将每个星号替换为任意字符串（可为空）得到名称 $m$，则称 $p$ 匹配 $m$。注意不同星号可被替换为不同字符串。 给定 $\mathrm{N}$ 个模式，请构造一个长度不超过 $10^{4}$ 的字符串，使其同时匹配所有给定模式；若不存在这样的字符串，则报告无解。

输入第一行包含测试用例数 $\mathrm{T}$。随后每个测试用例包含： - 第一行：整数 $\mathrm{N}$ 表示模式数量 - 随后 $\mathrm{N}$ 行：每行一个字符串 $\mathrm{P}_{\mathrm{i}}$ 表示第 $\mathrm{i}$ 个模式

对于每个测试用例，输出一行 `Case #x: y`，其中： - $x$ 为测试用例编号（从 1 开始） - $y$ 为满足条件的长度不超过 $10^{4}$ 的字符串，若无解则输出 `*`

样例 #1 中，其他可行解包括 COCOCONUTS 和 ILIKECOCONUTS，但 COCONUTSAREGREAT 和 COCOANUTS 不符合要求。注意同一模式可能在测试用例中重复出现。 样例 #2 无解，故输出 `*`。 以下情况不会出现在测试集 1，但可能出现在测试集 2 或 3： ``` 4 H*O HELLO* *HELLO HE* ``` 可行解包括 HELLO 和 HELLOGOODBYEHELLO，但 OTHELLO 和 HELLOO 不符合。 ``` 2 CO*DE J*AM ``` 无解，输出 `*`。 ``` 2 CODE* *JAM ``` CODEJAM 是可行解之一。 以下情况仅可能出现在测试集 3： ``` 2 A*C*E *B*D* ``` 可行解包括 ABCDE 和 ABUNDANCE，但 BOLDFACE 不符合。 ``` 2 A*C*E *B*D ``` 无解，输出 `*`。 **数据范围** - $1 \leqslant \mathrm{T} \leqslant 100$ - $2 \leqslant \mathrm{N} \leqslant 50$ - $2 \leqslant \mathrm{P}_{\mathrm{i}}$ 长度 $\leqslant 100$ - 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含大写字母和星号 - 每个 $\mathrm{P}_{\mathrm{i}}$ 至少包含一个大写字母 **测试集 1（5 分，可见判果）** - 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含一个星号 - 星号必须位于模式开头 **测试集 2（5 分，可见判果）** - 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含一个星号 **测试集 3（18 分，可见判果）** - 每个 $\mathrm{P}_{\mathrm{i}}$ 至少含一个星号 翻译由 DeepSeek V3 完成