Description

你正在为一些孩子举办一个聚会，并为他们准备了一个蛋糕，蛋糕的形状是一个 $R$ 行 $C$ 列的网格。你的助手已经开始装饰蛋糕，在每个孩子的首字母上用糖霜写在蛋糕的某一个格子里。每个格子最多只包含一个首字母，并且没有两个孩子的首字母相同，因此每个首字母在蛋糕上只出现一次。

每个孩子都希望得到一块包含自己首字母且不包含其他孩子首字母的矩形（与网格对齐）蛋糕。你能否为蛋糕上的每一个空白格子分配归属，使得每个孩子都能得到满足要求的蛋糕块？保证一定存在可行解。蛋糕不需要平均分配，甚至有的孩子可能只得到 $1 \times 1$ 的小块；这将是关于不公平的宝贵人生课程。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为两个整数 $R$ 和 $C$。接下来 $R$ 行，每行 $C$ 个字符，表示蛋糕的网格。每个字符要么是一个大写英文字母（表示你的助手已经在该格子写上了这个字母），要么是 ?（表示该格子为空）。

Output Format

对于每组测试数据，输出一行 Case #x:，其中 $x$ 是当前测试数据的编号（从 1 开始）。然后输出 $R$ 行，每行 $C$ 个字符，表示你分配后的蛋糕网格。你的输出网格必须与输入网格相同，只不过将所有的 ? 替换为大写英文字母，表示该格子属于哪个孩子的蛋糕块。你不能添加输入中没有出现过的字母。在你的输出网格中，对于每个字母，所有包含该字母的格子必须组成一个与网格对齐的矩形区域。

3
3 3
G??
?C?
??J
3 4
CODE
????
?JAM
2 2
CA
KE

Case #1:
GGJ
CCJ
CCJ
Case #2:
CODE
COAE
JJAM
Case #3:
CA
KE

Hint

样例解释

样例输出展示了样例数据的一组可行解。其他解也是可能的。

数据范围

• $1 \leq T \leq 100$。
• 输入网格中至少有一个字母。
• 每个字母最多只在一个格子中出现一次。
• 保证每组测试数据都至少有一个解。

小数据范围（8 分，测试点 1 - 可见）

• $1 \leq R \leq 12$。
• $1 \leq C \leq 12$。
• $R \times C \leq 12$。

大数据范围（13 分，测试点 2 - 隐藏）

• $1 \leq R \leq 25$。
• $1 \leq C \leq 25$。

由 ChatGPT 4.1 翻译