Bajtazar 正在玩一个益智游戏。游戏区域是一个由 $n \times m$ 个方格组成的矩形。每个方格要么是空的，要么包含一个白色或黑色的方块。

在每一步操作中，可以将游戏区域向平行于矩形边的四个方向之一倾斜。此时，所有的方块都会沿着该方向尽可能地移动，直到碰到矩形的边界或另一个方块为止。

Bajtazar 执行了一系列操作。请给出他执行完最后一次操作后的游戏状态。

输入格式

第一行包含两个整数，表示游戏区域的尺寸：高度 $n$ 和宽度 $m$ ($1 \le n, m \le 500$)。

接下来的 $n$ 行描述了初始状态，按从上到下的顺序排列。每行包含 $m$ 个字符，描述了该行从左到右的初始状态。每个字符要么是点号 ‘.’（表示该方格为空），要么是字母 ‘B’ 或 ‘C’（分别表示白色或黑色方块）。

下一行包含一个整数 $k$ ($1 \le k \le 500\,000$)，表示 Bajtazar 执行的操作次数。

最后一行包含一个长度为 $k$ 的字符串，描述了 Bajtazar 执行的操作序列。该字符串由字母 ‘G’、‘D’、‘L’、‘P’ 组成，分别代表向上、向下、向左或向右移动。

输出格式

输出最终的游戏状态，格式与初始状态相同，即输出 $n$ 行，每行包含 $m$ 个字符，字符为 ‘.’、‘B’ 或 ‘C’。

样例

输入 1

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

输出 1

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

说明 1

样例解释：在第一次操作 ‘G’ 后，所有方块向上滑动，游戏状态变为：

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

在第二次操作 ‘L’ 后，方块向左滑动，游戏状态变为：

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

在最后一次操作 ‘P’ 后，方块向右滑动，游戏状态变为样例输出所示。