시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 71 19 13 31.707%

문제

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.....
W3sicHJvYmxlbV9pZCI6IjMxOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUiLCJkZXNjcmlwdGlvbiI6IjxwPk54Tlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc3NCBcdWMxMzhcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZDZjXHVjNWVkXHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YWM3MFx1YjA5OCBcdWJjYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViZTQ4IFx1YWQ2Y1x1YzVlZCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwXHViMjk0IFx1YWNmNVx1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWM3NDAgXHVjOTExXHViODI1XHVjNzU4IFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWJjMWJcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDU2ZFx1YzBjMSBcdWJjYmRcdWM3NzRcdWIwOTggXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YmMxNFx1YjJlNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YjYxMFx1YjI5NCBcdWMyZGNcdWFjYzQgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyA5MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YmNiZFx1YWNmYyBcdWFjZjVcdWIzYzQgXHVhYzhjXHVjNzg0XHVkMzEwXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ2OGNcdWM4MDRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWQ2OGNcdWM4MDRcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNFx1YzVkMCBcdWFjZjVcdWM3NDAgXHVjOTExXHViODI1XHVjNzU4IFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWJjMWJcdWM1NDQgXHViY2JkXHVjNzc0XHViMDk4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NDQgXHViOWNjXHViMGEwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDQgXHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYTggXHVkNmM0IFx1YzJkY1x1YWNjNCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjJlNFx1YzJkYyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYTRcdWIyOTQgXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9sb3B0YS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTFweDsgd2lkdGg6NTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQ0IFx1YzhmY1x1YzViNFx1YzljNCBcdWIzMDBcdWI4NWMgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE4oMSAmbGU7IE4gJmxlOyAxMDAwKVx1YWNmYyBcdWQ2OGNcdWM4MDRcdWM3NDQgXHVkNTVjIFx1ZDY5Zlx1YzIxOCBLKDEgJmxlOyBLICZsZTsgNTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1YzBhY1x1YWMwMVx1ZDYxNSwgJiMzOTtYJiMzOTtcdWIyOTQgXHViY2JkLCAmIzM5O0wmIzM5O1x1Yzc0MCBcdWFjZjVcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1ZDY4Y1x1YzgwNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7TCYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5O0QmIzM5O1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7TCYjMzk7XHVjNzQwIFx1YzJkY1x1YWNjNCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgJiMzOTtEJiMzOTtcdWIyOTQgXHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IEtcdWJjODhcdWM3NTggXHVkNjhjXHVjODA0XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI5YzhcdWNlNWMgXHVkNmM0XHVjNzU4IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibG9wdGEiLCJkZXNjcmlwdGlvbiI6IjxwPkdhbWUgYm9hcmQgY29uc2lzdHMgb2YgTnhOIHNtYWxsIHNxdWFyZXMgYXJyYW5nZWQgaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuIEEgc3F1YXJlIGNhbiBiZSBlbXB0eSBvciBvY2N1cGllZCBieSBhIHdhbGwuIFRoZXJlIGlzIGEgYmFsbCBpbiBvbmUgZW1wdHkgc3F1YXJlIG9uIHRoZSBib2FyZC4gQmFsbCBpcyB1bmRlciB0aGUgaW5mbHVlbmNlIG9mIGdyYXZpdHksIHNvIGl0IG11c3QgYWx3YXlzIGxpZSBvbiBhIHdhbGwgb3Igb24gdGhlIGZsb29yIG9mIHRoZSBnYW1lIGJvYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBjYW4gcm90YXRlIHRoZSBnYW1lIGJvYXJkIDkwIGRlZ3JlZXMgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2UuIFdhbGxzIGFuZCB0aGUgYmFsbCBhcmUgcm90YXRpbmcgdG9nZXRoZXIgd2l0aCB0aGUgd2hvbGUgYm9hcmQuIEFmdGVyIHRoZSByb3RhdGlvbiwgdGhlIGJhbGwgZHJvcHMgZG93biAoaW5mbHVlbmNlZCBieSBncmF2aXR5KSBvbiB0aGUgZmlyc3Qgd2FsbCB1bmRlciBpdCAob3Igb24gdGhlIGZsb29yIG9mIHRoZSBib2FyZCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV4YW1wbGUgb2YgYSBib2FyZCBmaXJzdCByb3RhdGVkIGNsb2Nrd2lzZSBhbmQgdGhlbiBjb3VudGVyY2xvY2t3aXNlOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9sb3B0YS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTFweDsgd2lkdGg6NTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIGxheW91dCBvZiB0aGUgYm9hcmQgYWZ0ZXIgYSBzZXF1ZW5jZSBvZiBnaXZlbiByb3RhdGlvbnMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIEssIDEgJmxlOyBOICZsZTsgMTAwMCwgMSAmbGU7IEsgJmxlOyA1MDAsMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHRoZSBpbml0aWFsIGRlc2NyaXB0aW9uIG9mIHRoZSBib2FyZDogJiMzOTsuJiMzOTsgKGRvdCkgZGVub3RlcyBlbXB0eSBzcXVhcmUsICYjMzk7WCYjMzk7IGRlbm90ZXMgd2FsbCwgYW5kICYjMzk7TCYjMzk7IHRoZSBpbml0aWFsIHBvc2l0aW9uIG9mIHRoZSBiYWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgSyBsaW5lcyB0aGVyZSBpcyBvbmUgY2hhcmFjdGVyLCBlaXRoZXIgJiMzOTtMJiMzOTsgb3IgJiMzOTtEJiMzOTssIHJlcHJlc2VudGluZyB0aGUgZGlyZWN0aW9uIG9mIHJvdGF0aW9uIGluIHRoZSBjb3JyZXNwb25kaW5nIHN0ZXAuICYjMzk7TCYjMzk7IG1lYW5zIGNvdW50ZXJjbG9ja3dpc2UgYW5kICYjMzk7RCYjMzk7IG1lYW5zIGNsb2Nrd2lzZSByb3RhdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OIGxpbmVzIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbGF5b3V0IG9mIHRoZSBib2FyZCBhZnRlciBhbGwgSyBnaXZlbiByb3RhdGlvbnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d