시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjNmIwXHViOWFjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1IFx1YjYxMFx1YjI5NCBcdWMyZGNcdWFjYzQgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyA5MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWJjYmRcdWFjZmMgXHVhY2Y1XHViM2M0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNjhjXHVjODA0XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNjhjXHVjODA0XHVjNzc0IFx1YjA1ZFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVhY2Y1XHVjNzQwIFx1YzkxMVx1YjgyNVx1Yzc1OCBcdWM2MDFcdWQ1YTVcdWM3NDQgXHViYzFiXHVjNTQ0IFx1YmNiZFx1Yzc3NFx1YjA5OCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHViYzE0XHViMmU1XHVjNzQ0IFx1YjljY1x1YjBhMCBcdWI1NGNcdWFlNGNcdWM5YzAgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWM3NDAgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQ0IFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4IFx1ZDZjNCBcdWMyZGNcdWFjYzQgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWIyZTRcdWMyZGMgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE0XHViMjk0IFx1YzYwOFx1YzJkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvbG9wdGEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTExcHg7IHdpZHRoOjU3N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMzAwXHViODVjIFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhOCBcdWM3NzRcdWQ2YzRcdWM3NTggXHVjMGMxXHVkMGRjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWFjZmMgXHVkNjhjXHVjODA0XHVjNzQ0IFx1ZDU1YyBcdWQ2OWZcdWMyMTggSygxICZsZTsgSyAmbGU7IDUwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjICYjMzk7LiYjMzk7XHVjNzQwIFx1YmU0OCBcdWMwYWNcdWFjMDFcdWQ2MTUsICYjMzk7WCYjMzk7XHViMjk0IFx1YmNiZCwgJiMzOTtMJiMzOTtcdWM3NDAgXHVhY2Y1XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExY1x1Yzc1OCBcdWQ2OGNcdWM4MDQgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAmIzM5O0wmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTtEJiMzOTtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmIzM5O0wmIzM5O1x1Yzc0MCBcdWMyZGNcdWFjYzQgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsICYjMzk7RCYjMzk7XHViMjk0IFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1YzViNFx1YzljNCBLXHViYzg4XHVjNzU4IFx1ZDY4Y1x1YzgwNFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViOWM4XHVjZTVjIFx1ZDZjNFx1Yzc1OCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVjMGMxXHVkMGRjXHViOTdjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImxvcHRhIiwiZGVzY3JpcHRpb24iOiI8cD5HYW1lIGJvYXJkIGNvbnNpc3RzIG9mIE54TiBzbWFsbCBzcXVhcmVzIGFycmFuZ2VkIGluIE4gcm93cyBhbmQgTiBjb2x1bW5zLiBBIHNxdWFyZSBjYW4gYmUgZW1wdHkgb3Igb2NjdXBpZWQgYnkgYSB3YWxsLiBUaGVyZSBpcyBhIGJhbGwgaW4gb25lIGVtcHR5IHNxdWFyZSBvbiB0aGUgYm9hcmQuIEJhbGwgaXMgdW5kZXIgdGhlIGluZmx1ZW5jZSBvZiBncmF2aXR5LCBzbyBpdCBtdXN0IGFsd2F5cyBsaWUgb24gYSB3YWxsIG9yIG9uIHRoZSBmbG9vciBvZiB0aGUgZ2FtZSBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgY2FuIHJvdGF0ZSB0aGUgZ2FtZSBib2FyZCA5MCBkZWdyZWVzIGNsb2Nrd2lzZSBvciBjb3VudGVyY2xvY2t3aXNlLiBXYWxscyBhbmQgdGhlIGJhbGwgYXJlIHJvdGF0aW5nIHRvZ2V0aGVyIHdpdGggdGhlIHdob2xlIGJvYXJkLiBBZnRlciB0aGUgcm90YXRpb24sIHRoZSBiYWxsIGRyb3BzIGRvd24gKGluZmx1ZW5jZWQgYnkgZ3Jhdml0eSkgb24gdGhlIGZpcnN0IHdhbGwgdW5kZXIgaXQgKG9yIG9uIHRoZSBmbG9vciBvZiB0aGUgYm9hcmQpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FeGFtcGxlIG9mIGEgYm9hcmQgZmlyc3Qgcm90YXRlZCBjbG9ja3dpc2UgYW5kIHRoZW4gY291bnRlcmNsb2Nrd2lzZTombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvbG9wdGEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTExcHg7IHdpZHRoOjU3N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBsYXlvdXQgb2YgdGhlIGJvYXJkIGFmdGVyIGEgc2VxdWVuY2Ugb2YgZ2l2ZW4gcm90YXRpb25zLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOIGFuZCBLLCAxICZsZTsgTiAmbGU7IDEwMDAsIDEgJmxlOyBLICZsZTsgNTAwLDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIE4gbGluZXMgY29udGFpbiB0aGUgaW5pdGlhbCBkZXNjcmlwdGlvbiBvZiB0aGUgYm9hcmQ6ICYjMzk7LiYjMzk7IChkb3QpIGRlbm90ZXMgZW1wdHkgc3F1YXJlLCAmIzM5O1gmIzM5OyBkZW5vdGVzIHdhbGwsIGFuZCAmIzM5O0wmIzM5OyB0aGUgaW5pdGlhbCBwb3NpdGlvbiBvZiB0aGUgYmFsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBvZiB0aGUgZm9sbG93aW5nIEsgbGluZXMgdGhlcmUgaXMgb25lIGNoYXJhY3RlciwgZWl0aGVyICYjMzk7TCYjMzk7IG9yICYjMzk7RCYjMzk7LCByZXByZXNlbnRpbmcgdGhlIGRpcmVjdGlvbiBvZiByb3RhdGlvbiBpbiB0aGUgY29ycmVzcG9uZGluZyBzdGVwLiAmIzM5O0wmIzM5OyBtZWFucyBjb3VudGVyY2xvY2t3aXNlIGFuZCAmIzM5O0QmIzM5OyBtZWFucyBjbG9ja3dpc2Ugcm90YXRpb24uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+TiBsaW5lcyBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGxheW91dCBvZiB0aGUgYm9hcmQgYWZ0ZXIgYWxsIEsgZ2l2ZW4gcm90YXRpb25zLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==