2026

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из $m$ строк и $n$ столбцов. Доска разбита на $m \times n$ единичных клеток размером $1 \times 1$. На некоторых клетках стоят квадратные фишки размером $1 \times 1$, на каждой фишке написана одна из $26$ английских букв.

С фишками производятся $q$ операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой $s$ длины $q$, состоящей из символов, соответствующих направлениям: <<L>> --- влево, <<R>> --- вправо, <<U>> --- вверх и <<D>> --- вниз.

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

Определите, как будет выглядеть доска после выполнения всех операций.

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число $t$ --- количество наборов входных данных в тесте ($1 \le t \le 200\,000$). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа $m$ и $n$ --- размеры доски ($1 \le m, n \le 10^6$, $1 \le m\times n \le 10^6$).

В следующих $m$ строках задано изначальное расположение фишек на доске.

В $i$-й строке ($1 \le i \le m$) находится строка $a_{i1}a_{i2}\ldots a_{in}$ длины $n$, задающая $i$-ю строку доски. Каждый символ $a_{ij}$ является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если $a_{ij}=$<<.>>, то клетка в $i$-й строке и $j$-м столбце является пустой, иначе в ней находится фишка, на которой написана буква $a_{ij}$.

В последней строке заданы $q$ символов $s_1s_2\ldots s_q$ без пробелов, задающие последовательность операций ($1 \le q \le 10^6$). Каждый символ $s_i$ является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений $m \times n$ по всем наборам входных данных не превышает $2\cdot 10^6$. Сумма значений $q$ по всем наборам входных данных не превышает $2\cdot 10^6$.

Для каждого набора входных данных выведите итоговое расположение фишек на доске после выполнения всех операций в том же формате, что и во входных данных.

В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как $s_1=$<<L>>. После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как $s_2=$<<R>>. После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как $s_3=$<<U>>. После ее выполнения доска будет выглядеть следующим образом: