题目描述

译自 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$ 是样例。

子任务	分值	附加限制	子任务依赖
$1$	$9$	$t=1$, $q=1$, $n,m\le 100$
$2$	$7$	$s_i \neq \texttt{D}$, $s_i \neq \texttt{U}$
$3$	$13$	$\sum mnq \le 10^7$	$1$
$4$	$14$	$s_i \neq \texttt{D}$	$2$
$5$	$12$	棋盘上每个字符都为 $\texttt{a}$，$\sum mq \le 10^7$
$6$	$11$	棋盘上每个字符都为 $\texttt{a}$	$5$
$7$	$9$	棋盘的初始状态为「阶梯状」
$8$	$14$	$s$ 是 $\texttt{LURD}$ 重复若干次
$9$	$11$		$1-8$