C. Тропа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во Флориде нет гор, и мужчина из Флориды не может осознать их существование. Ему действительно нужна ваша помощь в этом деле.

Среди дикой природы находится горная местность, представленная в виде прямоугольной сетки с $$$n$$$ строками и $$$m$$$ столбцами. Каждая ячейка в сетке в соответствии с её положением обозначается $$$(i, j)$$$, где $$$i$$$ — индекс строки, а $$$j$$$ — индекс столбца. Высота ячейки $$$(i, j)$$$ обозначается $$$a_{i,j}$$$.

Однако в этом регионе произошли некоторые изменения. Путь, состоящий из $$$n + m - 1$$$ ячеек, начинающийся в левом верхнем углу $$$(1, 1)$$$ и заканчивающийся в правом нижнем углу $$$(n, m)$$$, был очищен. Иными словами, для каждой ячейки $$$(i, j)$$$ вдоль этого пути высота $$$a_{i,j}$$$ была установлена равной $$$0$$$. Каждая ячейка пути находится либо на одну ячейку ниже предыдущей ($$$\mathtt{D}$$$), либо на одну ячейку правее ($$$\mathtt{R}$$$).

Известно, что до того, как в регион были внесены изменения, он обладал магическим свойством: все строки и все столбцы имели одинаковую сумму высот. Более формально, существует целое число $$$x$$$ такое, что $$$\sum_{j=1}^m a_{i, j} = x$$$ для всех $$$1\le i\le n$$$, и $$$\sum_{i=1}^n a_{i, j} = x$$$ для всех $$$1\le j\le m$$$.

Ваша задача состоит в том, чтобы назначить новые высоты ячейкам на пути таким образом, чтобы вышеупомянутое магическое свойство было восстановлено. Можно доказать, что решение всегда существует. Если существует несколько решений, удовлетворяющих данному свойству, выведите любое из них.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n, m \leq 1000$$$) — количество строк и столбцов в таблице.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n+m-2$$$ ($$$s_i = \mathtt{D}$$$ или $$$s_i = \mathtt{R}$$$) — шаги, которые путь выполняет от $$$(1, 1)$$$ до $$$(n, m)$$$. Символ $$$\mathtt{D}$$$ представляет собой шаг вниз, а $$$\mathtt{R}$$$ представляет шаг вправо.

В $$$i$$$-й из следующих $$$n$$$ строк содержится по $$$m$$$ целых чисел $$$a_{i,1}, a_{i, 2}, \ldots, a_{i,m}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$) — высота ячеек сетки. Гарантируется, что если ячейка $$$(i, j)$$$ лежит на пути, то $$$a_{i,j} = 0$$$.

Гарантируется, что сумма значений $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите $$$n$$$ строк по $$$m$$$ целых чисел, представляющих восстановленную сетку высот $$$b_{i, j}$$$. Высоты должны удовлетворять $$$-10^{15} \leq b_{i,j} \leq 10^{15}$$$, и дополнительно $$$a_{i,j} = b_{i,j}$$$, если $$$(i, j)$$$ не находится на пути. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
4
3 3
DRRD
0 2 3
0 0 0
3 1 0
4 5
DRRRRDD
0 1 0 2 3
0 0 0 0 0
-1 0 -3 -3 0
0 0 0 -1 0
2 3
RRD
0 0 0
0 1 0
5 5
DDDDRRRR
0 25 2 9 11
0 6 13 20 22
0 17 24 1 8
0 3 10 12 19
0 0 0 0 0
Выходные данные
1 2 3
2 3 1
3 1 2
-6 1 0 2 3
7 -1 3 2 -11
-1 0 -3 -3 7
0 0 0 -1 1
0 -1 1
0 1 -1
18 25 2 9 11
4 6 13 20 22
15 17 24 1 8
21 3 10 12 19
7 14 16 23 5
Примечание

В первом наборе входных данных сетка была заполнена таким образом, чтобы каждая строка и каждый столбец содержали числа $$$1, 2, 3$$$ в некотором порядке, что приводит к общей сумме $$$6$$$.

Во втором наборе входных данных сетка была заполнена таким образом, что сумма в каждой строке и в каждом столбце равнялась $$$0$$$.