有一块 $$$n\times m$$$ 的棋盘,分为多个单元。这个板上还有一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的单元格(即共享一条边的两个单元格),并且没有两个多米诺骨牌重叠。
Piet 认为这块板子太无聊了,需要重新上漆。他会将多米诺骨牌的单元格涂成黑色和白色。如果满足以下所有条件,他称这幅画为美丽的:
- 对于每个多米诺骨牌,其一个单元格被漆成白色,另一个单元格被漆成黑色;
- 对于每一行,该行中黑色单元格的数量等于该行中白色单元格的数量;
- 对于每一列,该列中黑色单元格的数量等于该列中白色单元格的数量。
请注意,没有被多米诺骨牌覆盖的单元格根本不被绘制,它们既不被视为黑色也不被视为白色。
帮助皮特创作一幅美丽的画作,或者告诉他这是不可能的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,如果一幅美丽的画不存在,则输出一个整数 $$$-1$$$。否则,打印 $$$n$$$ 行,每行包含 $$$m$$$ 个字符,描述一幅美丽画作的相应行中的颜色。与未被多米诺骨牌覆盖的单元相对应的每个字符都必须是 。 (一个点),如果相应的单元格为黑色,则所有其他字符必须为 B;如果相应的单元格为白色,则所有其他字符必须为 W。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 4 6 ..LR.. ULRU.. DLRDUU ..LRDD 5 4 .LR. .UU. UDDU D..D LR.. 2 2 .. ..
输出 #1
..WB.. WWBB.. BBWWWB ..BWBW -1 .. ..
注意
在第一个测试用例中,答案如下所示:
在第二个测试用例中,不可能以正确的方式绘制所有单元格。