题目背景

翻译自 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
.......

提示

样例解释：

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

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

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

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