Ball

A square game board made of N x N square cells is standing upright. Each cell is either empty or a wall, and one empty cell contains a ball. Because the ball is affected by gravity, it always rests on top of a wall or on the bottom edge of the board.

You may rotate the board 90 degrees clockwise or counterclockwise at a time. The walls and the ball rotate together with the board. After the rotation finishes, gravity acts on the ball again, and the ball falls until it touches a wall or the bottom edge of the board.

The figure below illustrates rotating the board clockwise and then rotating it back counterclockwise.

Print the state of the board after performing all given rotations.

The first line contains the board size N(1 <= N <= 1000) and the number of rotations K(1 <= K <= 500,000).

The next N lines describe the initial board. . means an empty cell, X means a wall, and L means the initial position of the ball.

Each of the following K lines contains one character, L or D, describing the direction of that rotation. L means counterclockwise, and D means clockwise.

Print N lines showing the board after all K rotations have been performed in order.