시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 313 108 77 30.800%

문제

작고 특이한 모양의 유성 사진이 인터넷에 올라왔다. 사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다. 유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 이를 복원해야 한다.

유성 사진을 문자의 배열로 단순화시켜 표기할 것이다. 문자 'X'는 유성의 일부를, 문자 '#'는 땅의 일부를, 그리고 나머지(공기)는 문자 '.'로 이루어져 있다.

모든 유성 조각들은 연결되어 있다. 즉, 두 부분 유성이 존재한다면, 한 쪽에서 유성 조각을 통해 상하좌우로 이동해서 다른 부분 유성에 도달할 수 있다. 땅 또한 같은 방식으로 연결되어 있다.

주어진 사진에서 유성은 땅보다 위에 있다. 정확히 말하자면, 적어도 한 줄 이상의 공기('.')가 존재하며, 유성은 그 보다 위에, 땅은 그 보다 아래쪽에 있다. 또한, 사진의 맨 밑 줄은 모두 땅이다.

유성은 수직으로 낙하한다. 유성이 땅에 떨어졌을 때, 유성과 땅은 원형을 유지한다고 한다. 유성이 떨어진 후의 사진을 복구하여라.

입력

첫 번째 줄에는 각각 사진의 세로와 가로 길이를 의미하는 정수 R과 S (3 ≤ R, S ≤ 3 000)가 주어진다.

다음 R 개의 줄에는 문자로 단순화된 사진이 주어진다.

출력

유성이 떨어지고 난 뒤의 사진(크기 R × S)을 복원하여 출력하라.

예제 입력 1

5 6
.XXXX.
...X..
......
#..###
######

예제 출력 1

......
.XXXX.
...X..
#..###
######

예제 입력 2

9 7
XXX.XXX
X.XXX.X
X..X..X
X.....X
.......
.#...#.
.##.##.
.#####.
#######

예제 출력 2

.......
.......
.......
.......
XXX.XXX
X#XXX#X
X##X##X
X#####X
#######
W3sicHJvYmxlbV9pZCI6IjEwNzAzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzIwXHVjMTMxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3OTFcdWFjZTAgXHVkMmI5XHVjNzc0XHVkNTVjIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWM3MjBcdWMxMzEgXHVjMGFjXHVjOWM0XHVjNzc0IFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzVkMCBcdWM2MmNcdWI3N2NcdWM2NTRcdWIyZTQuIFx1YzBhY1x1YzljNFx1YzVkMFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHViMTkyXHVjNzQwIFx1YWNmM1x1YzVkMFx1YzExYyBcdWI1YThcdWM1YjRcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzcyMFx1YzEzMVx1Yzc3NCBcdWQ1YzhcdWFjZjVcdWM1ZDAgXHVjYzBkXHVkNjAwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjNzIwXHVjMTMxXHVjNzc0IFx1YjVhOFx1YzViNFx1YzljMFx1YWNlMCBcdWIwOWMgXHViNGE0XHVjNzU4IFx1YzBhY1x1YzljNFx1YjNjNCBcdWM3ODhcdWM1YzhcdWM5YzBcdWI5Y2MgXHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjXHViM2M0IFx1YzE4Y1x1YzJlNFx1YjNmY1x1YmM4NFx1YjgyNCBcdWM3NzRcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVjMTMxIFx1YzBhY1x1YzljNFx1Yzc0NCBcdWJiMzhcdWM3OTBcdWM3NTggXHViYzMwXHVjNWY0XHViODVjIFx1YjJlOFx1YzIxY1x1ZDY1NFx1YzJkY1x1Y2YxYyBcdWQ0NWNcdWFlMzBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiMzhcdWM3OTAgJiMzOTtYJiMzOTtcdWIyOTQgXHVjNzIwXHVjMTMxXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjk3YywgXHViYjM4XHVjNzkwICYjMzk7IyYjMzk7XHViMjk0IFx1YjU0NVx1Yzc1OCBcdWM3N2NcdWJkODBcdWI5N2MsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwOThcdWJhMzhcdWM5YzAoXHVhY2Y1XHVhZTMwKVx1YjI5NCBcdWJiMzhcdWM3OTAgJiMzOTsuJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzcyMFx1YzEzMSBcdWM4NzBcdWFjMDFcdWI0ZTRcdWM3NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWI0NTAgXHViZDgwXHViZDg0IFx1YzcyMFx1YzEzMVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1ZDU1YyBcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNzIwXHVjMTMxIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzExYyBcdWIyZTRcdWI5NzggXHViZDgwXHViZDg0IFx1YzcyMFx1YzEzMVx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTQ1IFx1YjYxMFx1ZDU1YyBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWMwYWNcdWM5YzRcdWM1ZDBcdWMxMWMgXHVjNzIwXHVjMTMxXHVjNzQwIFx1YjU0NVx1YmNmNFx1YjJlNCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViOWQwXHVkNTU4XHVjNzkwXHViYTc0LCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YzkwNCBcdWM3NzRcdWMwYzFcdWM3NTggXHVhY2Y1XHVhZTMwKCYjMzk7LiYjMzk7KVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAsIFx1YzcyMFx1YzEzMVx1Yzc0MCBcdWFkZjggXHViY2Y0XHViMmU0IFx1YzcwNFx1YzVkMCwgXHViNTQ1XHVjNzQwIFx1YWRmOCBcdWJjZjRcdWIyZTQgXHVjNTQ0XHViNzk4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWMwYWNcdWM5YzRcdWM3NTggXHViOWU4IFx1YmMxMSBcdWM5MDRcdWM3NDAgXHViYWE4XHViNDUwIFx1YjU0NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVjMTMxXHVjNzQwIFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWIwOTlcdWQ1NThcdWQ1NWNcdWIyZTQuIFx1YzcyMFx1YzEzMVx1Yzc3NCBcdWI1NDVcdWM1ZDAgXHViNWE4XHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzIwXHVjMTMxXHVhY2ZjIFx1YjU0NVx1Yzc0MCBcdWM2ZDBcdWQ2MTVcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzIwXHVjMTMxXHVjNzc0IFx1YjVhOFx1YzViNFx1YzljNCBcdWQ2YzRcdWM3NTggXHVjMGFjXHVjOWM0XHVjNzQ0IFx1YmNmNVx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWMwYWNcdWM5YzRcdWM3NTggXHVjMTM4XHViODVjXHVjNjQwIFx1YWMwMFx1Yjg1YyBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOCBSXHVhY2ZjIFMgKDMgJmxlOyBSLCBTICZsZTsgMyAwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFIgXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWI4NWMgXHViMmU4XHVjMjFjXHVkNjU0XHViNDFjIFx1YzBhY1x1YzljNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzIwXHVjMTMxXHVjNzc0IFx1YjVhOFx1YzViNFx1YzljMFx1YWNlMCBcdWIwOWMgXHViNGE0XHVjNzU4IFx1YzBhY1x1YzljNChcdWQwNmNcdWFlMzAgUiAmdGltZXM7IFMpXHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA3MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNRVRFT1IiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcGhvdG9ncmFwaCBvZiBhIHNtYWxsIG1ldGVvciBvZiBhbiB1bnVzdWFsIHNoYXBlIHdhcyBwb3N0ZWQgb24gdGhlIEludGVybmV0LiBJbiB0aGF0IHBob3RvLCB0aGUgbWV0ZW9yIGlzIGZhbGxpbmcgZnJvbSBhIGdyZWF0IGhlaWdodCB0b3dhcmRzIGFuIHVuZXZlbiBncm91bmQuIFRoZXJlIHdhcyBhbHNvIGEgcGhvdG9ncmFwaCB0YWtlbiBqdXN0IGFmdGVyIHRoZSBtZXRlb3IgZmVsbCwgYnV0IGl0IGlzIHNhZGx5IGxvc3QgYW5kIG5lZWRzIHRvIGJlIHJlY29uc3RydWN0ZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBwaG90b2dyYXBoIGlzIHNpbXBsaWZpZWQgYW5kIHJlcHJlc2VudGVkIGFzIGEgbWF0cml4IG9mIGNoYXJhY3RlcnMuIFRoZSBjaGFyYWN0ZXIgJmxzcXVvO1gmcnNxdW87IHJlcHJlc2VudHMgYSBwYXJ0IG9mIHRoZSBtZXRlb3IsIHRoZSBjaGFyYWN0ZXIgJmxzcXVvOyMmcnNxdW87IHJlcHJlc2VudHMgYSBwYXJ0IG9mIHRoZSBncm91bmQgYW5kIHRoZSByZXN0IG9mIHRoZSBpbWFnZSAoYWlyKSBjb25zaXN0cyBvZiB0aGUgY2hhcmFjdGVycyAmbHNxdW87LiZyc3F1bzsuPFwvcD5cclxuXHJcbjxwPlRoZSBtZXRlb3IgaXMgY29ubmVjdGVkLiBJbiBvdGhlciB3b3JkcywgYSBwYXRoIGV4aXN0cyBiZXR3ZWVuIGVhY2ggdHdvIHBhcnRzIG9mIHRoZSBtZXRlb3IgdGhhdCBwYXNzZXMgb25seSB0aHJvdWdoIHRoZSBtZXRlb3IgYW5kIGNvbnNpc3RzIG9mIHN0ZXBzIHVwLCBkb3duLCBsZWZ0IGFuZCByaWdodC4gQWxzbywgYWxsIHBhcnRzIG9mIHRoZSBncm91bmQgYXJlIGNvbm5lY3RlZCBpbiB0aGUgc2FtZSB3YXkuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBnaXZlbiBwaG90b2dyYXBoLCB0aGUgbWV0ZW9yIGlzIGxvY2F0ZWQgc3RyaWN0bHkgYWJvdmUgZ3JvdW5kLiBNb3JlIHByZWNpc2VseSwgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIHJvdyBvZiBhaXIgKGRvdHMpLCB0aGUgbWV0ZW9yIGlzIGNvbXBsZXRlbHkgYWJvdmUgaXQgYW5kIHRoZSBncm91bmQgaXMgY29tcGxldGVseSBiZWxvdyBpdC4gSW4gYWRkaXRpb24sIHRoZSBlbnRpcmUgYm90dG9tIHJvdyBvZiB0aGUgaW1hZ2UgaXMgYSBwYXJ0IG9mIHRoZSBncm91bmQuPFwvcD5cclxuXHJcbjxwPlRoZSBtZXRlb3Igd2FzIGZhbGxpbmcgdmVydGljYWxseSBkb3dud2FyZC4gV2hlbiBpdCBmZWxsIG9uIHRoZSBncm91bmQsIGl0IGtlcHQgaXRzIHNoYXBlLCBhbmQgdGhlIHNhbWUgZ29lcyBmb3IgdGhlIGdyb3VuZC4gUmVjb25zdHJ1Y3QgdGhlIHBob3RvZ3JhcGggYWZ0ZXIgdGhlIG1ldGVvciBmYWxsITxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXJzIFIgYW5kIFMgKDMgJmxlOyBSLCBTICZsZTsgMyAwMDApLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIHRoZSBudW1iZXIgb2YgY29sdW1ucyBvZiB0aGUgcGhvdG9ncmFwaC48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW4gdGhlIHBob3RvZ3JhcGggZGVzY3JpYmVkIGluIHRoZSB0YXNrLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgcmVxdWlyZWQgcGhvdG9ncmFwaCAoZGltZW5zaW9ucyBSICZ0aW1lczsgUykgYWZ0ZXIgdGhlIG1ldGVvciBmYWxsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==