CF1863D.Two-Colored Dominoes

There is an $n\times m$ board divided into cells. There are also some dominoes on this board. Each domino covers two adjacent cells (that is, two cells that share a side), and no two dominoes overlap.

Piet thinks that this board is too boring and it needs to be painted. He will paint the cells of the dominoes black and white. He calls the painting beautiful if all of the following conditions hold:

• for each domino, one of its cells is painted white and the other is painted black;
• for each row, the number of black cells in this row equals the number of white cells in this row;
• for each column, the number of black cells in this column equals the number of white cells in this column.

Note that the cells that are not covered by dominoes are not painted at all, they are counted as neither black nor white.

Help Piet produce a beautiful painting or tell that it is impossible.

有一个 $n\times m$ 的棋盘，被划分为若干单元格。棋盘上还放置了一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的单元格（即共享一条边的两个单元格），且任意两个多米诺骨牌互不重叠。

Piet 认为这个棋盘太过单调，需要进行染色。他将对多米诺骨牌所覆盖的单元格染成黑色或白色。若一种染色方案满足以下所有条件，则称其为优美的：

• 对于每个多米诺骨牌，其覆盖的两个单元格中一个染成白色、另一个染成黑色；
• 对于每一行，该行中黑色单元格的数量等于白色单元格的数量；
• 对于每一列，该列中黑色单元格的数量等于白色单元格的数量。

注意：未被多米诺骨牌覆盖的单元格完全不染色，既不计入黑色单元格，也不计入白色单元格。

请帮助 Piet 构造一种优美的染色方案，或判定其不存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\le n, m\le 500$).

The next $n$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $m$ characters, describing the cells in the corresponding row from left to right. Each character is one of U, D, L, R, or ., meaning that the cell is covered with a top, bottom, left, right half of a domino or nothing, respectively. The tiling is guaranteed to be valid.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $250\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2\le n, m\le 500$）。

接下来的 $n$ 行自上而下逐行描述棋盘的铺砌方式。每行包含 $m$ 个字符，自左至右描述对应行中的各个格子。每个字符为 U、D、L、R 或 . 中的一个，分别表示该格子被一个骨牌的上半部分、下半部分、左半部分、右半部分覆盖，或未被覆盖。题目保证铺砌方式合法。

保证所有测试用例的 $n \cdot m$ 之和不超过 $250\,000$。

For each test case, output a single integer $-1$ if a beautiful painting does not exist. Otherwise, print $n$ lines, each containing $m$ characters, describing the colors in the corresponding row of a beautiful painting. Every character corresponding to a cell not covered by a domino must be . (a dot), and all other characters must be B if the corresponding cell is black or W if it is white.

If there are multiple solutions, print any of them.

对于每个测试用例，若不存在优美的涂色方案，则输出单个整数 $-1$；否则，输出 $n$ 行，每行包含 $m$ 个字符，描述一幅优美涂色方案中对应行的颜色。每个未被多米诺骨牌覆盖的单元格对应字符必须为 .（一个英文句点），其余所有字符若对应单元格为黑色则为 B，若为白色则为 W。

若存在多种解法，输出任意一种即可。

In the first test case, the answer is illustrated below:

In the second test case, it is impossible to paint all cells the right way.

在第一个测试用例中，答案如下图所示：

在第二个测试用例中，无法以正确的方式将所有格子涂色。