No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

译自 ROI 2024 Day1 T2. 2026

在 2026 年，一款名为《2026》的新型棋盘游戏在一个由 $m$ 行 $n$ 列的矩形棋盘上进行。这个棋盘分为 $m \times n$ 个大小为 $1 \times 1$ 的小格子。在一些格子中放置着大小同样为 $1 \times 1$ 的方块棋子，每个棋子上标记有 $26$ 个英文字母中的一个。

游戏中包含 $q$ 次操作，每次操作将所有棋子向四个基本方向之一（左、右、上、下）移动至边界。因此，操作序列由长度为 $q$ 的字符串 $s$ 给出，该字符串由四个字符组成：$\texttt{L}$ —— 向左，$\texttt{R}$ —— 向右，$\texttt{U}$ —— 向上，$\texttt{D}$ —— 向下。

具体操作如下：只要棋盘上有至少一个棋子并且该方向的相邻格子为空，该棋子就会向那个空格子移动。

请确定所有操作完成后棋盘的样子。

输入

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 2\cdot 10^5)$，表示数据组数。每组数据的格式如下：

第一行包含两个整数 $m,n\ (1 \le m, n \le 10^6, 1 \le m \times n \le 10^6)$。

接下来的 $m$ 行描述了棋盘上棋子的初始位置。

第 $i\ (1 \le i \le m)$ 行包含长度为 $n$ 的字符串 $a_{i1}a_{i2}\ldots a_{in}$，代表棋盘第 $i$ 行。每个字符 $a_{ij}$ 要么是小写英文字母 $\texttt{a}$ 到 $\texttt{z}$，要么是点 $\texttt{.}$ 表示空格，即第 $i$ 行第 $j$ 列的格子为空。

最后一行提供了长度为 $q$ 的字符串 $s_1s_2\ldots s_q$，无空格，表示操作序列（$1 \le q \le 10^6$）。每个字符 $s_i$ 是 $\texttt{L},\texttt{R},\texttt{U}, \texttt{D}$ 中的一个。

所有输入数据组的 $m \times n$ 值之和不超过 $2 \cdot 10^6$。所有输入数据组的 $q$ 之和不超过 $2 \cdot 10^6$。

输出

对于每组输入数据，在执行所有操作后，以与输入数据相同的格式输出棋子在棋盘上的最终位置。

4
4 4
.a.b
..e.
....
.cd.
LRU
1 1
.
UULLRRDD
1 6
.a.aa.
LLURDDD
5 7
.ba.b..
ac..c.d
e......
....da.
d.eae..
DLDDRULRRR

..ab
..ce
...d
....
.
...aaa
dceebab
...aeac
.....ad
......d
.......

在第一组输入数据中，棋盘最初看起来是这样的：

第一次操作将所有棋子向左移动，因为 $s_1=\texttt{L}$。执行后，棋盘将如下所示：

第二次操作将所有棋子向右移动，因为 $s_2=\texttt{R}$。执行后，棋盘将如下所示：

第三次也是最后一次操作将所有棋子向上移动，因为 $s_3=\texttt{U}$。执行后，棋盘将如下所示：

数据范围

令 $\sum mnq$ 表示所有输入数据组的 $mnq$ 之和。令 $\sum mq$ 表示所有输入数据组的 $mq$ 之和。

如果 $m=n$，对于所有 $1 \le i \le j \le n$，$a_{ij}=\texttt{.}$，对于所有 $1 \le j < i \le n$，$a_{ij}\neq \texttt{.}$，则称棋盘为「阶梯状」。换句话说，所有棋子都位于棋盘主对角线以下的单元格上，并且每个主对角线以下的单元格上都有一个棋子。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。