시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 65 15 11 28.205%

문제

NxN개의 정사각형 구역으로 이루어진 정사각형 모양의 게임판이 세워져 있다. 각각의 구역은 비어있거나 벽으로 이루어져 있고, 빈 구역 중 하나에는 공이 놓여있다. 이 공은 중력의 영향을 받기 때문에 항상 벽이나 게임판의 바닥 위에 있게 된다.

우리는 게임판을 시계 방향 또는 시계 반대 방향으로 90도 회전시킬 수 있다. 이 때 벽과 공도 게임판과 같이 회전하게 된다. 회전이 끝난 후에 공은 중력의 영향을 받아 벽이나 게임판의 바닥을 만날 때까지 떨어진다.

다음은 게임판을 시계 방향으로 회전시킨 후 시계 반대 방향으로 다시 회전시키는 예시이다.

게임판을 주어진 대로 회전시킨 이후의 상태를 출력하시오.

입력

첫째 줄에 게임판의 크기 N(1 ≤ N ≤ 1000)과 회전을 한 횟수 K(1 ≤ K ≤ 500,000)가 주어진다.

다음 N개의 줄에는 게임판의 초기 상태가 주어진다. 여기서 '.'은 빈 사각형, 'X'는 벽, 'L'은 공의 초기 위치를 의미한다.

이후 K개의 줄에는 각 단계에서의 회전 방향을 나타내는 'L' 또는 'D'가 주어진다. 'L'은 시계 반대 방향을 의미하고, 'D'는 시계 방향을 의미한다.

출력

주어진 K번의 회전을 순서대로 마친 후의 게임판의 상태를 N개의 줄에 걸쳐 출력한다.

예제 입력

6 2
....XX
X.....
......
..L...
.XXX..
......
L
D

예제 출력

....XX
X.....
......
......
.XXX..
L.....

힌트