该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

$\texttt{Albert Li}$ 觉得这个棋盘太无聊了，需要给它涂色。他打算将多米诺骨牌覆盖的格子涂成黑色和白色。他称涂色是美丽的，当且仅当满足以下所有条件：

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

注意，没有被多米诺骨牌覆盖的格子不进行涂色，也不计入黑色或白色格子的数量。

请你帮助 $\texttt{Albert Li}$ 给棋盘涂出一种美丽的方案，或者告诉他不可能做到。

Format

Input

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。

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

接下来的 $n$ 行描述棋盘的铺牌情况，从上到下依次给出每一行。每行包含 $m$ 个字符，描述该行从左到右的各个格子。每个字符为 $\texttt{U、D、L、R}$ 或 $\texttt{.}$，分别表示该格子被多米诺骨牌的上、下、左、右半部分覆盖，或没有被覆盖。保证铺牌方案合法。

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

Output

对于每个测试用例，如果不存在美丽的涂色方案，输出一个整数 $-1$。否则，输出 $n$ 行，每行 $m$ 个字符，描述美丽涂色方案中对应行的颜色。未被多米诺骨牌覆盖的格子用 $\texttt{.}$（点号）表示，其余格子用 $\texttt{B}$ 表示黑色，$\texttt{W}$ 表示白色。

如果有多种方案，输出任意一种均可。

Samples

3
4 6
..LR..
ULRU..
DLRDUU
..LRDD
5 4
.LR.
.UU.
UDDU
D..D
LR..
2 2
..
..

..WB..
WWBB..
BBWWWB
..BWBW
-1
..
..

Note

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

在第二个测试用例中，不可能将所有格子按要求正确涂色。