The new Tatar game "2026" is played on a rectangular grid board consisting of $m$ rows and $n$ columns. The board is divided into $m \times n$ unit cells of size $1 \times 1$. Some cells contain square tokens of size $1 \times 1$, and each token has one of the 26 English letters written on it.

There are $q$ operations performed on the tokens. Each operation consists of moving all tokens as far as possible in one of four directions. Thus, the sequence of operations is given by a string $s$ of length $q$, consisting of characters corresponding to the directions: "L" — left, "R" — right, "U" — up, and "D" — down.

An operation is performed as follows: as long as there is at least one token on the board for which the adjacent cell in the given direction is empty, this token moves to that adjacent cell.

Determine what the board will look like after all operations are completed.

Input

Each test consists of several test cases. The first line of the test contains an integer $t$ — the number of test cases ($1 \le t \le 200\,000$). The following are the descriptions of the test cases. Each test case is described as follows:

The first line of the test case contains integers $m$ and $n$ — the dimensions of the board ($1 \le m, n \le 10^6$, $1 \le m \times n \le 10^6$).

The next $m$ lines specify the initial arrangement of tokens on the board.

In the $i$-th line ($1 \le i \le m$) there is a string $a_{i1}a_{i2} \dots a_{in}$ of length $n$, specifying the $i$-th row of the board. Each character $a_{ij}$ is either a lowercase English letter from "a" to "z" or a dot ".". If $a_{ij} = \text{"."}$, then the cell in the $i$-th row and $j$-th column is empty; otherwise, it contains a token with the letter $a_{ij}$ written on it.

The last line contains $q$ characters $s_1s_2 \dots s_q$ without spaces, specifying the sequence of operations ($1 \le q \le 10^6$). Each character $s_i$ is one of the characters "L", "R", "U", or "D".

The sum of $m \times n$ over all test cases does not exceed $2 \cdot 10^6$. The sum of $q$ over all test cases does not exceed $2 \cdot 10^6$.

Output

For each test case, output the final arrangement of tokens on the board after all operations are completed in the same format as in the input.

Subtasks

Let $\sum mnq$ be the sum of $mnq$ over all test cases. Let $\sum mq$ be the sum of $mq$ over all test cases. We call an arrangement of tokens a "staircase" if $m = n$, $a_{ij} = \text{"."}$ for all $1 \le i \le j \le n$, and $a_{ij} \neq \text{"."}$ for all $1 \le j < i \le n$. In other words, all tokens are located in cells below the main diagonal of the board, and every cell below the main diagonal contains a token.

Examples

Input 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

Output 1

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

Note

In the first test case from the example, the board initially looks like this:

The first operation moves all tokens to the left, since $s_1 = \text{"L"}$. After it is performed, the board looks as follows:

The second operation moves all tokens to the right, since $s_2 = \text{"R"}$. After it is performed, the board looks as follows:

The third and final operation moves all tokens up, since $s_3 = \text{"U"}$. After it is performed, the board looks as follows: