重力矩阵

题目描述

Y 同学正在观察一个 $N \times M$ 的字符矩阵。矩阵中的每个单元格要么包含一个小写英文字母，要么包含一个字符 .（表示空白）。

这个矩阵会经历 $K$ 个阶段的重力变化。在每个阶段，重力会指向四个基本方向之一：左（L）、右（R）、上（U）、下（D）。

当重力指向某个方向时，矩阵中的所有字母都会向该方向滑动，直到它们遇到矩阵边界或被其他字母阻挡为止。在滑动过程中，同一行或同一列中字母的相对顺序保持不变。

例如，若重力向下（D），则每一列的字母都会落向该列的底部，紧密堆叠，其上方的空间变为空白。

你的任务是，根据给定的重力变化序列，计算出经过 $K$ 个阶段后，矩阵的最终形态。

输入格式

第一行包含三个整数 $N, M, K$，分别表示矩阵的行数、列数和重力变化的阶段数。

第二行包含一个长度为 $K$ 的字符串，仅由字符 L, R, U, D 组成，按顺序描述了每个阶段的重力方向。

接下来的 $N$ 行，每行包含 $M$ 个字符，描述初始的矩阵状态。

输出格式

输出 $N$ 行，每行 $M$ 个字符，表示所有操作结束后矩阵的最终状态。

样例

样例输入 #1

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

样例输出 #1

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

样例输入 #2

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

样例输出 #2

a..
.b.
..x

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N, M \le 100$
• $0 \le K \le 100$
• 矩阵仅包含小写英文字母和字符 .。