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$.