AT_arc219_e [ARC219E] Equal Distribution

有一个形状为 $2H \times 2W$ 的蛋糕，蛋糕每个格子用 $(i,j)$ 表示，其中 $i$ 表示从上往下的第 $i$ 行，$j$ 表示从左往右的第 $j$ 列。如果 $S_{i,j}=$ 'o'，则 $(i,j)$ 位置上有一颗草莓；如果 $S_{i,j}=$ 'x'，则该格没有草莓。保证恰好有 $2HW$ 个格子上有草莓。 请将蛋糕的每个格子分配到 A、B 两个区域中，分配需要满足如下所有要求： - 任意一个格子必须且仅属于 A、B 两个区域之一。 - 区域 A、B 都是连通的。即，对任何属于同一区域中的两个格子，可以只经过与该区域内的相邻格子（共享边）多次移动，从其中一个格子移动到另一个格子。 - 区域 A、B 各恰好包含 $2HW$ 个格子。 - 区域 A、B 各恰好包含 $HW$ 颗草莓。 可以证明，总存在一种分割方式满足上述所有条件。 你将会得到 $T$ 组测试数据，请依次解答每组数据。

输入通过标准输入给出，格式如下： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据的格式如下： > $H$ $W$ > $S_{1,1} S_{1,2} \ldots S_{1,2W}$ > $S_{2,1} S_{2,2} \ldots S_{2,2W}$ > $\vdots$ > $S_{2H,1} S_{2H,2} \ldots S_{2H,2W}$

请按顺序输出每组测试数据的答案，每组之间用换行分隔。 对于每组测试数据，输出格式如下： > $X_{1,1} X_{1,2} \ldots X_{1,2W}$ > $X_{2,1} X_{2,2} \ldots X_{2,2W}$ > $\vdots$ > $X_{2H,1} X_{2H,2} \ldots X_{2H,2W}$ 其中，若 $(i,j)$ 属于区域 A，则 $X_{i,j}$ 输出 'A'；否则输出 'B'。 如果有多种合法分区方案，输出任意一种均可。

### 样例解释 1 以第一个测试数据为例。 在样例输出中，区域 A、B 都是连通的且各有两个格子。同时区域 A 包含了 $(1,1)$ 位置的草莓，区域 B 包含了 $(2,2)$ 位置的草莓。 另外，例如如下输出也是合法解： ``` AB AB ``` ### 数据范围 - $1 \leq T$ - $1 \leq H \leq W$ - $H \times W \leq 10^6$ - $S_{i,j}$ 为 'o' 或 'x' - 恰好有 $2HW$ 个 $(i,j)$ 满足 $S_{i,j}=$ 'o' - 所有测试数据中 $\sum H \times W \leq 10^6$ - $T, H, W$ 均为整数。 由 ChatGPT 5 翻译