Олимпиадный тренинг

Задача . D. Двухцветные доминошки

Задача

Темы: жадные алгоритмы Конструктив *1400

Доска $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, если она белая.

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

Примечание

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