一种新的鞑靼游戏“2026”在由 $m$ 行 $n$ 列组成的矩形网格棋盘上进行。棋盘被划分为 $m \times n$ 个 $1 \times 1$ 的单位格。某些格子上放置有 $1 \times 1$ 的方形棋子，每个棋子上写有一个 26 个英文字母中的一个。

棋子会进行 $q$ 次操作。每次操作包括将所有棋子向四个方向之一移动到底。因此，操作序列由长度为 $q$ 的字符串 $s$ 指定，其中字符对应方向：“L”表示向左，“R”表示向右，“U”表示向上，“D”表示向下。

操作执行方式如下：只要棋盘上至少有一个棋子，其在指定方向上的相邻格子是空的，该棋子就会移动到那个相邻的格子上。

请确定在执行所有操作后棋盘的样子。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $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} = \text{“.”}$，则第 $i$ 行第 $j$ 列的格子为空，否则该格子上有一个写着字母 $a_{ij}$ 的棋子。

最后一行包含 $q$ 个字符 $s_1s_2 \dots s_q$（无空格），指定操作序列 ($1 \le q \le 10^6$)。每个字符 $s_i$ 是“L”、“R”、“U”或“D”之一。

所有测试用例中 $m \times n$ 的总和不超过 $2 \cdot 10^6$。所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^6$。

输出格式

对于每个测试用例，输出执行所有操作后棋盘上棋子的最终位置，格式与输入格式相同。

子任务

记 $\sum mnq$ 为所有测试用例中 $mnq$ 的总和。 记 $\sum mq$ 为所有测试用例中 $mq$ 的总和。 如果 $m = n$，且对于所有 $1 \le i \le j \le n$ 都有 $a_{ij} = \text{“.”}$，且对于所有 $1 \le j < i \le n$ 都有 $a_{ij} \neq \text{“.”}$，则称棋子的布局为“阶梯状”。换句话说，所有棋子都位于棋盘主对角线下方，且主对角线下方的每个格子上都有一个棋子。

样例

输入格式 1

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

输出格式 1

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

说明

在第一个测试用例中，棋盘初始状态如下：

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

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

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