AT_arc219_e.Equal Distribution

There is a shortcake in the shape of a $2H \times 2W$ grid. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i,j)$. Cell $(i,j)$ has one strawberry on it if $S_{i,j}=$ o, and nothing if $S_{i,j}=$ x. It is guaranteed that exactly $2HW$ cells have strawberries.

Divide each cell of this shortcake into regions A and B so that all of the following conditions are satisfied:

• Every cell belongs to exactly one of regions A and B.
• Both regions A and B are connected. That is, for any two cells in the same region, one can move between them by repeatedly moving to an adjacent cell (sharing an edge) in the same region.
• Both regions A and B contain exactly $2HW$ cells each.
• Both regions A and B contain exactly $HW$ strawberries each.

It can be proved that such a partition always exists.

You are given $T$ test cases; solve each of them.

有一个形状为 $2H \times 2W$ 网格的蛋糕。从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作格子 $(i,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$ 组测试数据；请对每组数据求解。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$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}$

输入从标准输入中按以下格式给出：

$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}$

Output your solutions for the test cases in order, separated by newlines.

For each test case, output your solution in the following format:

$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}$

Here, $X_{i,j}$ is A if cell $(i,j)$ belongs to region A, and B if it belongs to region B.

If multiple valid partitions exist, any of them will be accepted.

按测试用例的顺序输出你的解答，各解答之间用换行符分隔。

对于每个测试用例，请按以下格式输出你的解答：

$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，则 $X_{i,j}$ 为 B。

若存在多个合法划分方案，输出任意一种即可。

Sample 1 Explanation:
Consider the first test case.

In the sample output, both regions A and B are connected and contain two cells each. Also, region A contains the strawberry at cell $(1,1)$, and region B contains the strawberry at cell $(2,2)$.

Additionally, for example, the following output is accepted:

Constraints

• $1\le T$
• $1\le H\le W$
• $H\times W\le 10^6$
• $S_{i,j}$ is o or x.
• There are exactly $2HW$ pairs $(i,j)$ with $S_{i,j}=$ o.
• The sum of $H\times W$ over all test cases is at most $10^6$.
• $T, H, W$ are integers.

样例 1 解释：
考虑第一个测试用例。

在样例输出中，区域 A 和区域 B 均为连通区域，且各自包含两个格子。此外，区域 A 包含位于格子 $(1,1)$ 的草莓，区域 B 包含位于格子 $(2,2)$ 的草莓。

另外，例如以下输出也是可接受的：

约束条件

• $1\le T$
• $1\le H\le W$
• $H\times W\le 10^6$
• $S_{i,j}$ 为 o 或 x。
• 恰好有 $2HW$ 对 $(i,j)$ 满足 $S_{i,j}=$ o。
• 所有测试用例的 $H\times W$ 之和不超过 $10^6$。
• $T, H, W$ 均为整数。