lopta

문제

Game board consists of NxN small squares arranged in N rows and N columns. A square can be empty or occupied by a wall. There is a ball in one empty square on the board. Ball is under the influence of gravity, so it must always lie on a wall or on the floor of the game board. 

We can rotate the game board 90 degrees clockwise or counterclockwise. Walls and the ball are rotating together with the whole board. After the rotation, the ball drops down (influenced by gravity) on the first wall under it (or on the floor of the board). 

Example of a board first rotated clockwise and then counterclockwise: 

[이미지 1]

Write a program that will determine the layout of the board after a sequence of given rotations. 

입력

First line of input contains integers N and K, 1 ≤ N ≤ 1000, 1 ≤ K ≤ 500,000. 

Following N lines contain the initial description of the board: '.' (dot) denotes empty square, 'X' denotes wall, and 'L' the initial position of the ball. 

In each of the following K lines there is one character, either 'L' or 'D', representing the direction of rotation in the corresponding step. 'L' means counterclockwise and 'D' means clockwise rotation. 

출력

N lines of output should contain the layout of the board after all K given rotations.