Bajtazar is playing with a puzzle. It is a rectangle composed of $n \times m$ squares. Each square can be empty or contain a white or black tile.

In each move, the toy can be tilted in one of four directions parallel to the sides of the rectangle. Then, all tiles slide in that direction as far as possible, without going outside the rectangle or overlapping each other.

Bajtazar has performed a sequence of moves. Determine the state of the puzzle after the last move he made.

Input

The first line of the input contains the dimensions of the puzzle: height $n$ and width $m$ ($1 \le n, m \le 500$).

The next $n$ lines describe the initial state, row by row from top to bottom. Each line contains $m$ symbols describing the initial state of one row of the puzzle, from left to right. Each symbol is either a dot '.', meaning the square is empty, or the letter 'B' or 'C', representing a white or black tile, respectively.

The next line of the input contains the number $k$ ($1 \le k \le 500\,000$), representing the number of moves performed by Bajtazar.

The last line of the input contains a string of length $k$ describing the sequence of moves performed by Bajtazar. The string consists of the letters 'G', 'D', 'L', 'P', representing a move up, down, left, or right, respectively.

Output

The output should contain the final state of the puzzle, in the same format as the initial state, i.e., using $n$ lines, each containing $m$ symbols '.', 'B', or 'C'.

Examples

Input 1

4 5
.....
.B.C.
..C..
...B.
3
GLP

Output 1

..BCC
....B
.....
.....

Note

Explanation of the example: After the first move 'G', all tiles slide up and the state of the puzzle looks like this:

.BCC.
...B.
.....
.....

After the second move 'L', the tiles slide to the left and the state of the puzzle looks like this:

BCC..
B....
.....
.....

After the last, third move 'P', the tiles slide to the right and the state of the puzzle looks like the example output.