Description

Martin 正在听一场关于线性代数的讲座。毋庸置疑，正在讲课的教授是整个宇宙中最无聊的人。黑板上写着一个 $N \times M$ 的矩阵。矩阵中的某些位置是字母（英文字母），而其他位置是空白。下面是一个 $6 \times 8$ 的矩阵示例：

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

Martin 完全不知道这个矩阵代表什么。他太无聊了，已经有 30 分钟没有听讲了。不过，Martin 有着极其丰富的想象力。他想象这个矩阵突然受到了重力的影响，所有字母都会向下滑动，直到每个字母“到达底部”或“碰到它下方的字母”为止。在第一阶段，上面的矩阵会变成：

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

之后，重力改变了方向，现在把字母拉向左边。我们进入了第二阶段。同样，所有字母都会向左滑动，直到每个字母“到达左括号”或“碰到它左边的字母”为止。前面的矩阵变为：

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

Martin 在脑海中不断进行这个过程，直到这场无聊的讲座结束。当然，在每个阶段之后，也就是所有字母都到达各自位置后，重力可能会改变方向（方向有四种可能：左、右、上和下）。

任务

编写一个程序，根据重力方向变化的精确序列，确定所有字母在矩阵中的最终位置。

Input Format

第一行包含三个整数 $N$、$M$ 和 $K$，其中 $N \times M$ 是矩阵的大小，$K$ 是阶段的数量。

第二行包含一个长度为 $K$ 的字符串，由字母 L、R、U 和 D 组成，分别表示每个阶段重力的方向（左、右、上和下）。

接下来的 $N$ 行表示矩阵。每行包含 $M$ 个字符。字符为小写英文字母或 .（点号），表示空白位置。

Output Format

输出 Martin 在讲座结束时得到的矩阵。矩阵的格式与输入数据完全相同。

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

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

3 3 0
a..
.b.
..x

a..
.b.
..x

Hint

输入范围

• $1 \leq N, M \leq 100$
• $0 \leq K \leq 100$

由 ChatGPT 4.1 翻译