Problem Description

This problem is translated from PA 2022 Round 4 Łamigłówka.

Byteasar is playing with a puzzle. It is a rectangle of size $n \times m$ made up of cells. Each cell may be empty, or contain a black or white block.

In each operation, the toy can be tilted in one of four directions parallel to the sides of the rectangle. Then all blocks slide in that direction as far as possible, without leaving the rectangle or overlapping.

Byteasar tilted it many times. Output the state of the whole puzzle after the last tilt.

Input Format

The first line contains two integers $n, m$, which represent the size of the rectangle.

The next $n$ lines each contain a string of length $m$, describing the initial state. The string contains only three kinds of characters: . means the cell is empty, B means the cell contains a white block, and C means the cell contains a black block.

The next line contains an integer $k$, which is the number of times Byteasar tilts the puzzle.

The last line contains a string of length $k$, describing the direction of each tilt. The string contains only G, D, L, P, which mean tilting up, down, left, and right, respectively.

Output Format

Output the final state of the toy, in the same format as the initial state: output $n$ lines, each a string of length $m$, containing only ., B, C.

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

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

Hint

For $100\%$ of the testdata, it holds that:

$1 \le n, m \le 500$, $1 \le k \le 5 \times 10 ^ 5$。

Translated by ChatGPT 5