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 D1T2。

一款新的游戏《2026》在一个 $m$ 行 $n$ 列的矩形盘面上进行。盘面被划分为 $m \times n$ 个 $1 \times 1$ 的小格子。在一些格子上放置了大小为 $1 \times 1$ 的方块，每个方块上写有一个英文字母。

你需要进行 $q$ 次操作，每次操作都是将所有方块向一个方向移动到底。因此，操作序列由一个长度为 $q$ 的字符串 $s$ 给出，字符串中每个字符表示一个方向：L 表示向左移，R 表示向右移，U 表示向上移，D 表示向下移。

具体操作与游戏《2048》相类似：在棋盘上，只要有一个方块在指定方向上相邻的格子是空的，该方块就会移动到该空格子上，包括它后面的那些方块也会连带着向那个方向一起移动，直到前方没有空格。

题目描述

给出棋盘的初始状态和操作序列，请确定所有操作执行完成后盘面的状态。

输入格式

输入包含多组数据。

• 第一行输入一个整数 $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$）包含一个长度为 $n$ 的字符串 $a_{i1}a_{i2}\dots a_{in}$，表示第 $i$ 行的盘面状态。
    • 每个字符 $a_{ij}$ 要么是小写英文字母（从 a 到 z），要么是点号 .。如果 $a_{ij}$ 是 .，则表示第 $i$ 行第 $j$ 列的格子为空，否则表示该格子上有一个标有字母 $a_{ij}$ 的方块。
  • 最后一行输入一个字符串 $s$，由 $q$ 个字符组成，表示操作的序列（$1 \le q \le 10^6$）。每个字符都是 L，R，U，D 之一。

所有测试数据中 $m \times n$ 的总和不超过 $2 \times 10^6$，$q$ 的总和不超过 $2 \times 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
.......

提示

样例解释：

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

第一次操作将所有方块向左移动。接着，盘面会变成这样：

第二次操作将所有方块向右移动。接着，盘面会变成这样：

第三次，也是最后一次操作将所有方块向上移动。所有操作结束后，盘面会变成这样：