시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB251745533.742%

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

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

예제 입력 2

10 7
..........
XXXXXXXXX.
..X.....X.
..X.....X.
........X.
........X.
...X....X.
...X....X.
.XXXXXXXX.
L.........
L
L
L
L
D
D
L

예제 출력 2

........X.
.X......X.
.X....XXX.
.XXX....X.
.X......X.
.X......X.
.X......X.
.X...L..X.
.XXXXXXXX.
..........

예제 입력 3

10 8
...XXX..XX
....XX...X
L....X..XX
X..X..X...
.......X..
..X.....X.
.X........
X...X.....
...X......
.....X....
D
L
D
L
D
D
D
L

예제 출력 3

....X.....
......X...
.....X...X
........X.
.X.....X..
..X.......
...X..X..X
XX..X.....
X...XX....
XXL.XXX...
W3sicHJvYmxlbV9pZCI6IjMxOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUiLCJkZXNjcmlwdGlvbiI6IjxwPk54Tlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc3NCBcdWMxMzhcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZDZjXHVjNWVkXHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YWM3MFx1YjA5OCBcdWJjYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViZTQ4IFx1YWQ2Y1x1YzVlZCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwXHViMjk0IFx1YWNmNVx1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWM3NDAgXHVjOTExXHViODI1XHVjNzU4IFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWJjMWJcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDU2ZFx1YzBjMSBcdWJjYmRcdWM3NzRcdWIwOTggXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YmMxNFx1YjJlNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YjYxMFx1YjI5NCBcdWMyZGNcdWFjYzQgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyA5MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YmNiZFx1YWNmYyBcdWFjZjVcdWIzYzQgXHVhYzhjXHVjNzg0XHVkMzEwXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ2OGNcdWM4MDRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWQ2OGNcdWM4MDRcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNFx1YzVkMCBcdWFjZjVcdWM3NDAgXHVjOTExXHViODI1XHVjNzU4IFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWJjMWJcdWM1NDQgXHViY2JkXHVjNzc0XHViMDk4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NDQgXHViOWNjXHViMGEwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDQgXHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYTggXHVkNmM0IFx1YzJkY1x1YWNjNCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjJlNFx1YzJkYyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYTRcdWIyOTQgXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2Q1ZDFmMDM3LTYzZjctNDBlZC1hNWY2LTNjZTcyYmI0YWFkN1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTYycHg7IGhlaWdodDogOTdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQ0IFx1YzhmY1x1YzViNFx1YzljNCBcdWIzMDBcdWI4NWMgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE4oMSAmbGU7IE4gJmxlOyAxMDAwKVx1YWNmYyBcdWQ2OGNcdWM4MDRcdWM3NDQgXHVkNTVjIFx1ZDY5Zlx1YzIxOCBLKDEgJmxlOyBLICZsZTsgNTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1YzBhY1x1YWMwMVx1ZDYxNSwgJiMzOTtYJiMzOTtcdWIyOTQgXHViY2JkLCAmIzM5O0wmIzM5O1x1Yzc0MCBcdWFjZjVcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1ZDY4Y1x1YzgwNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7TCYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5O0QmIzM5O1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7TCYjMzk7XHVjNzQwIFx1YzJkY1x1YWNjNCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgJiMzOTtEJiMzOTtcdWIyOTQgXHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IEtcdWJjODhcdWM3NTggXHVkNjhjXHVjODA0XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI5YzhcdWNlNWMgXHVkNmM0XHVjNzU4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibG9wdGEiLCJkZXNjcmlwdGlvbiI6IjxwPkdhbWUgYm9hcmQgY29uc2lzdHMgb2YgTnhOIHNtYWxsIHNxdWFyZXMgYXJyYW5nZWQgaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuIEEgc3F1YXJlIGNhbiBiZSBlbXB0eSBvciBvY2N1cGllZCBieSBhIHdhbGwuIFRoZXJlIGlzIGEgYmFsbCBpbiBvbmUgZW1wdHkgc3F1YXJlIG9uIHRoZSBib2FyZC4gQmFsbCBpcyB1bmRlciB0aGUgaW5mbHVlbmNlIG9mIGdyYXZpdHksIHNvIGl0IG11c3QgYWx3YXlzIGxpZSBvbiBhIHdhbGwgb3Igb24gdGhlIGZsb29yIG9mIHRoZSBnYW1lIGJvYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBjYW4gcm90YXRlIHRoZSBnYW1lIGJvYXJkIDkwIGRlZ3JlZXMgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2UuIFdhbGxzIGFuZCB0aGUgYmFsbCBhcmUgcm90YXRpbmcgdG9nZXRoZXIgd2l0aCB0aGUgd2hvbGUgYm9hcmQuIEFmdGVyIHRoZSByb3RhdGlvbiwgdGhlIGJhbGwgZHJvcHMgZG93biAoaW5mbHVlbmNlZCBieSBncmF2aXR5KSBvbiB0aGUgZmlyc3Qgd2FsbCB1bmRlciBpdCAob3Igb24gdGhlIGZsb29yIG9mIHRoZSBib2FyZCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV4YW1wbGUgb2YgYSBib2FyZCBmaXJzdCByb3RhdGVkIGNsb2Nrd2lzZSBhbmQgdGhlbiBjb3VudGVyY2xvY2t3aXNlOiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2Q1ZDFmMDM3LTYzZjctNDBlZC1hNWY2LTNjZTcyYmI0YWFkN1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTYycHg7IGhlaWdodDogOTdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIGxheW91dCBvZiB0aGUgYm9hcmQgYWZ0ZXIgYSBzZXF1ZW5jZSBvZiBnaXZlbiByb3RhdGlvbnMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIEssIDEgJmxlOyBOICZsZTsgMTAwMCwgMSAmbGU7IEsgJmxlOyA1MDAsMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHRoZSBpbml0aWFsIGRlc2NyaXB0aW9uIG9mIHRoZSBib2FyZDogJiMzOTsuJiMzOTsgKGRvdCkgZGVub3RlcyBlbXB0eSBzcXVhcmUsICYjMzk7WCYjMzk7IGRlbm90ZXMgd2FsbCwgYW5kICYjMzk7TCYjMzk7IHRoZSBpbml0aWFsIHBvc2l0aW9uIG9mIHRoZSBiYWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgSyBsaW5lcyB0aGVyZSBpcyBvbmUgY2hhcmFjdGVyLCBlaXRoZXIgJiMzOTtMJiMzOTsgb3IgJiMzOTtEJiMzOTssIHJlcHJlc2VudGluZyB0aGUgZGlyZWN0aW9uIG9mIHJvdGF0aW9uIGluIHRoZSBjb3JyZXNwb25kaW5nIHN0ZXAuICYjMzk7TCYjMzk7IG1lYW5zIGNvdW50ZXJjbG9ja3dpc2UgYW5kICYjMzk7RCYjMzk7IG1lYW5zIGNsb2Nrd2lzZSByb3RhdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OIGxpbmVzIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbGF5b3V0IG9mIHRoZSBib2FyZCBhZnRlciBhbGwgSyBnaXZlbiByb3RhdGlvbnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==