Description

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

Input Format

输入包含多组数据。

• 第一行输入一个整数 $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$。

Output Format

对于每组数据，输出执行完所有操作后的盘面，格式与输入相同。

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
.......

Hint

样例解释：

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

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

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

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