Letters

Martin is attending a lecture on linear algebra. Needless to say, the professor giving the lecture is the most boring person in the entire universe.

There is an $N \times M$ matrix written on the blackboard. Some entries are letters of the English alphabet, and the rest are blank. Here is an example of a $6 \times 8$ matrix:

$\begin{bmatrix} k & & l & & n & d & i & \\ & & & & & c & & \\ & & & & & & i & h \\ j & & & a & & & & \\ & & c & b & & & & \\ & & c & & & & e & f \end{bmatrix}$

Martin has no idea what the matrix represents. He has not followed the lecture for the last 30 minutes. Instead, he imagines that gravity suddenly acts on the matrix, and every letter slides downward until it either reaches the bottom or hits the letter below it. After the first phase, the matrix becomes:

$\begin{bmatrix} & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & l & & & i & & \\ k & & c & a & & d & i & h \\ j & & c & b & n & c & e & f \end{bmatrix}$

Then gravity changes direction and pulls the letters to the left. In this second phase, every letter slides left until it either reaches the left edge or hits the letter on its left. The matrix becomes:

$\begin{bmatrix} & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ l & i & & & & & & \\ k & c & a & d & i & h & & \\ j & c & b & n & c & e & f & \end{bmatrix}$

Martin continues this procedure in his head until the lecture ends. After each phase, once all letters have landed, gravity may change direction. The four possible directions are left, right, up, and down.

Write a program that finds the final position of every letter after the given sequence of gravity changes.

The first line contains three integers $N$, $M$, and $K$, where $N \times M$ is the size of the matrix and $K$ is the number of phases.

The second line contains a string of length $K$ made of the letters L, R, U, and D. They stand for the gravity direction in each phase: left, right, up, and down.

The next $N$ lines describe the matrix. Each line has $M$ characters, each either a lowercase English letter or '.' (a dot), which marks a blank entry.

Print the matrix after the last phase, in the same format as the input.

$1 \le N, M \le 100$

$0 \le K \le 100$