题目描述

题目译自 PA 2022 Runda 4 Łamigłówka

Byteasar 在玩拼图。它是一个由单元格组成的 $n \times m$ 大小的矩形。每个单元格可能是空的，也可能包含一个黑色或白色的方块。

在每次操作中，这个玩具可以向平行于矩形边的四个方向之一倾斜。然后所有的方块会朝那个方向滑动到最远可以所处的位置，而不超出矩形范围或重叠。

Byteasar 倾斜了多次，请给出倾斜最后一次后整个拼图的状态。

输入格式

第一行两个整数 $n, m$ ($1 \le n, m \le 500$)，表示这个矩形的大小。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，表示初始状态。字符串中仅包含三种字符：. 表示这个单元格是空的，B 表示这个单元格中有一个白色方块，C 表示这个单元格中有一个黑色方块。

接下来一行一个整数 $k$ ($1 \le k \le 500\,000$)，表示 Byteasar 倾斜的次数。

最后一行包含一个长为 $k$ 的字符串，表示 Byteasar 每次的倾斜方向。字符串中仅包含 G，D，L，P 四种字符，分别表示向上、向下、向左和向右倾斜。

输出格式

输出这个玩具的最终状态，输出格式与输入的初始状态格式相同，输出 $n$ 行，每行一个长度为 $m$ 的字符串，字符串中仅包含 .，B，C 三种字符。

4 5
.....
.B.C.
..C..
...B.
3
GLP

..BCC
....B
.....
.....

数据规模与约定

对于所有数据，保证：

$1 \le n, m \le 500$

$1 \le k \le 500,000$

初始状态和最终状态中仅包含字符 .、B、C

样例解释：

初始状态：

text
.....
.B.C.
..C..
...B.
第一次操作 G（向上）：

所有方块向上滑动到最远位置

操作后状态：


.BCC.
...B.
.....
.....
第二次操作 L（向左）：

所有方块向左滑动到最远位置

操作后状态：

BCC..
B....
.....
.....
第三次操作 P（向右）：

所有方块向右滑动到最远位置

最终状态：

..BCC
....B
.....
.....