D. Двухцветные доминошки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Доска $$$n\times m$$$ разделена на клетки. На этой доске также расположено несколько доминошек. Каждая доминошка покрывает две соседние клетки (то есть две клетки с общей стороной), и никакие две доминошки не пересекаются.

Пит считает, что эта доска очень скучная и что её надо покрасить. Он покрасит клетки доминошек в чёрный и белый цвета. Полученную раскраску он назовёт красивой, если будут выполнены все следующие условия:

  • у каждой доминошки одна клетка покрашена в чёрный цвет, а другая — в белый;
  • для каждой строки число чёрных клеток в этой строке равно числу белых клеток в этой строке;
  • для каждого столбца число чёрных клеток в этом столбце равно числу белых клеток в этом столбце.

Заметьте, что клетки, не покрытые доминошками, не покрашены вовсе и не считаются ни чёрными, ни белыми.

Помогите Питу получить красивую раскраску или скажите, что это невозможно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$, eсли красивой раскраски не существует. В противном случае выведите $$$n$$$ строк, каждая из которых состоит из $$$m$$$ символов и описывает цвета клеток в соответствующем ряду красивой раскраски. Каждый символ, соответствующий клетке, не покрытой доминошками, должен равняться . (точке), а каждый другой символ должен быть равен B, если соответствующая клетка чёрная, или W, если она белая.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
4 6
..LR..
ULRU..
DLRDUU
..LRDD
5 4
.LR.
.UU.
UDDU
D..D
LR..
2 2
..
..
Выходные данные
..WB..
WWBB..
BBWWWB
..BWBW
-1
..
..
Примечание

Ответ к первому набору входных данных изображён ниже:

Во втором наборе входных данных не существует правильной раскраски клеток.