Given an $n \times m$ matrix, each position may be empty or contain a lowercase letter.

You need to process $q$ operations, which are of four types:

• D: Gravity acts downwards, and all letters fall downwards. In other words, for each column, arrange the letters in that column at the bottom while maintaining their original relative order.
• U: Gravity acts upwards, and all letters "fall" upwards.
• L: Gravity acts to the left, and all letters "fall" to the left.
• R: Gravity acts to the right, and all letters "fall" to the right.

If the original matrix is:

.a.b.c
aabb..
..ccdd

Then after the operation L, it becomes:

abc...
aabb..
ccdd..

Output the state of the matrix after $q$ operations.

Input

The first line contains three positive integers $n, m, q$.

The second line contains a string of length $q$, consisting only of the characters D, U, L, and R.

The next $n$ lines each contain a string of length $m$, consisting only of lowercase letters and ., representing a row of the matrix.

Output

Output $n$ lines, each containing a string of length $m$, consisting only of lowercase letters and ., representing the final matrix.

Examples

Input 1

6 8 5
DLURD
k.l.ndi.
.....c..
......ih
j..a....
..cb....
..c...ef

Output 1

........
........
........
......hf
..iadice
.lkcbnjc

Constraints

For $30\%$ of the data, $1 \le n, m, q \le 10$.

For all data, $1 \le n, m, q \le 100$.