Sliding Puzzle Final Tilt

Byteasar is playing with a sliding puzzle. The puzzle is a rectangle of cells in an \( n \times m \) grid. Each cell is either empty or contains a black or white block.

In each move, the puzzle is tilted in one of the four directions parallel to the edges of the rectangle: left, right, up, or down. When the puzzle is tilted, all blocks slide as far as possible in that direction without leaving the grid or overlapping another block.

Byteasar performed several tilts. Your task is to compute and output the state of the puzzle after the final tilt.

The moves are applied sequentially, and the blocks slide each time according to the rules above.

Note: Black blocks and white blocks are treated the same in terms of sliding.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) where \( n \) and \( m \) represent the number of rows and columns of the puzzle, and \( k \) is the number of tilt operations.

The next \( n \) lines each contain a string of length \( m \) consisting of the characters . (empty cell), B (a black block), and W (a white block) representing the initial state of the puzzle.

The last line contains a string of \( k \) characters. Each character is one of L, R, U, or D, indicating a tilt left, right, up, or down, respectively.

outputFormat

Output \( n \) lines, each with a string of length \( m \), representing the state of the puzzle after all the tilt operations have been applied.

sample

3 4 1
.B.W
....
W..B
L

BW..
....
WB..