F. Понты
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В очередной скучный день карантина BThero принялся изучать матрицы размера $$$n \times m$$$. Строки матрицы нумеруются от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы нумеруются от $$$1$$$ до $$$m$$$ слева направо. Клетка в $$$i$$$-й строке и $$$j$$$-м столбце обозначается $$$(i, j)$$$.

Для каждой клетки $$$(i, j)$$$ матрицы у BThero были два значения:

  1. ценность данной клетки, которая выражается одним положительным целым числом;
  2. направление данной клетки, которое выражается одним из символов L, R, D, U. Данные символы означают переходы в соседние клетки $$$(i, j - 1)$$$, $$$(i, j + 1)$$$, $$$(i + 1, j)$$$, $$$(i - 1, j)$$$, соответственно. Никакой переход не вел за границу матрицы.

Назовем клетку $$$(i_2, j_2)$$$ достижимой из $$$(i_1, j_1)$$$, если, начав из клетки $$$(i_1, j_1)$$$ и переходя в соседнюю клетку в соответствии с направлением текущей клетки, мы рано или поздно посетим $$$(i_2, j_2)$$$.

BThero решил создать еще одну матрицу из имеющихся двух. Для клетки $$$(i, j)$$$ обозначим $$$S_{i, j}$$$ как множество достижимых из нее клеток (включая саму клетку $$$(i, j)$$$). Значение новой матрицы в клетке $$$(i, j)$$$ будет равно сумме ценностей всех клеток из $$$S_{i, j}$$$.

Быстро посчитав новую матрицу, BThero разослал ее всем своим друзьям. Однако он не сохранил обе изначальные матрицы! Помогите ему восстановить любые две изначальные матрицы, из которых могла получиться заданная.

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

В первой строке входного файла дано одно целое число $$$T$$$ ($$$1 \le T \le 100$$$) — кол-во наборов входных данных. Далее следуют $$$T$$$ наборов входных данных в следующем формате:

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \cdot m \le 10^5$$$).

Каждая из последующих $$$n$$$ строк содержит ровно $$$m$$$ целых чисел — элементы созданной матрицы. Все элементы находятся в отрезке $$$[2, 10^9]$$$.

Гарантируется, что $$$\sum{(n \cdot m)}$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора, если ответа не существует выведите одну единственную строку NO. Иначе выведите строку YES и две матрицы в таком же формате, как и во вводе.

  • Первая матрица должна быть матрицей ценностей, а вторая должна быть матрицей направлений.
  • Все числа в матрице ценностей должны быть положительными.
  • Все буквы в матрице направлений должны быть допустимыми. Никакой переход не должен указывать за границы матрицы.
Пример
Входные данные
2
3 4
7 6 7 8
5 5 4 4
5 7 4 4
1 1
5
Выходные данные
YES
1 1 1 1
2 1 1 1
3 2 1 1
R D L L
D R D L
U L R U
NO