시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 250 67 60 30.000%

문제

text-mode windows의 개발자인 동혁이는 "cascade mode (계단형 배치)" 부분을 코딩하다가 고심에 빠졌다. text-mode windows에서 하나의 window는 다음과 같이 ‘+’, ‘-’, ‘|’, ‘.’, 그리고 알파벳 소문자로 이루어져 있다.

+--|abcdef|---+
|.............|
|.............|
|.............|
|.............|
+-------------+

모든 window는 위와 같은 형태를 지키고 있으며, title을 기록할 수 있을 정도로 window는 넓다. (즉, title의 길이보다 모든 window는 적어도 6 이상은 가로로 길다. +-|, |-+가 들어가야 하므로) title은 가로로 정확히 가운데에 표시되어 있으며, 만일 위의 경우와 같이 window의 길이가 홀수인 경우 오른쪽이 왼쪽보다 하나 더 길다.

text-mode windows의 screen-shot이 주어졌다. 어떤 두 개의 window도 서로 겹치지 않게 배치되어 있다고 하자. 이때, 동혁이를 도와 다음과 같이 "cascade mode"로 window를 정리해 주는 프로그램을 작성하시오.

  1. 모든 window의 가로, 세로 크기는 변하지 않아야 한다.
  2. 모든 window들은 title의 알파벳 순서로 정렬한다.
  3. 모든 window들을 왼쪽 위 꼭짓점이 화면 전체의 왼쪽 위 꼭짓점이 되도록 옮긴다. 그리고 나서, 순서대로 한 칸씩 오른쪽 아래로 내려 배치한다.

입력

첫째 줄에 스크린의 세로 길이 M과 가로 길이 N이 주어진다. (10≤M, N≤100) 이어서 M개의 줄에는 각각 N개의 문자열이 주어지는데, 이는 screen-shot을 나타내 주는 정보이다. 배경 그림 같은 것은 없고 모두 ‘.’으로 표시되며, 모든 window의 title의 길이는 1 이상 10 이하이다. M과 N은 "cascade mode"로 window를 모두 정리할 수 있을 만큼 충분히 크다고 가정해도 좋다.

출력

M개의 줄에 걸쳐 "cascade mode"로 window를 모두 정리한 화면을 출력한다.

예제 입력 1

15 22
...............+-|a|-+
.+-|winamp|--+.|.....|
.|...........|.|.....|
.|...........|.|.....|
.|...........|.|.....|
.|...........|.|.....|
.+-----------+.|.....|
...............|.....|
+----|kit|----+|.....|
|.............||.....|
|.............||.....|
|.............||.....|
|.............|+-----+
|.............|.......
+-------------+.......

예제 출력 1

+-|a|-+...............
|+----|kit|----+......
||+-|winamp|--+|......
|||...........||......
|||...........||......
|||...........||......
|||...........||......
|++-----------++......
|.....|...............
|.....|...............
|.....|...............
|.....|...............
+-----+...............
......................
......................
W3sicHJvYmxlbV9pZCI6IjIwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJ3aW5kb3dzIiwiZGVzY3JpcHRpb24iOiI8cD50ZXh0LW1vZGUgd2luZG93c1x1Yzc1OCBcdWFjMWNcdWJjMWNcdWM3OTBcdWM3NzggXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0ICZxdW90O2Nhc2NhZGUgbW9kZSAoXHVhY2M0XHViMmU4XHVkNjE1IFx1YmMzMFx1Y2U1OCkmcXVvdDsgXHViZDgwXHViZDg0XHVjNzQ0IFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjJlNFx1YWMwMCBcdWFjZTBcdWMyZWNcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiB0ZXh0LW1vZGUgd2luZG93c1x1YzVkMFx1YzExYyBcdWQ1NThcdWIwOThcdWM3NTggd2luZG93XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgJmxzcXVvOysmcnNxdW87LCAmbHNxdW87LSZyc3F1bzssICZsc3F1bzt8JnJzcXVvOywgJmxzcXVvOy4mcnNxdW87LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4rLS18YWJjZGVmfC0tLStcclxufC4uLi4uLi4uLi4uLi58XHJcbnwuLi4uLi4uLi4uLi4ufFxyXG58Li4uLi4uLi4uLi4uLnxcclxufC4uLi4uLi4uLi4uLi58XHJcbistLS0tLS0tLS0tLS0tK1xyXG48XC9wcmU+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgd2luZG93XHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVkMGRjXHViOTdjIFx1YzljMFx1ZDBhNFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIHRpdGxlXHVjNzQ0IFx1YWUzMFx1Yjg1ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YzgxNVx1YjNjNFx1Yjg1YyB3aW5kb3dcdWIyOTQgXHViMTEzXHViMmU0LiAoXHVjOTg5LCB0aXRsZVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHViYWE4XHViNGUwIHdpbmRvd1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgNiBcdWM3NzRcdWMwYzFcdWM3NDAgXHVhYzAwXHViODVjXHViODVjIFx1YWUzOFx1YjJlNC4gKy18LCB8LStcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YykgdGl0bGVcdWM3NDAgXHVhYzAwXHViODVjXHViODVjIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWFjMDBcdWM2YjRcdWIzNzBcdWM1ZDAgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViOWNjXHVjNzdjIFx1YzcwNFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM2NDAgXHVhYzE5XHVjNzc0IHdpbmRvd1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVkNjQwXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzQgXHVjNjdjXHVjYWJkXHViY2Y0XHViMmU0IFx1ZDU1OFx1YjA5OCBcdWIzNTQgXHVhZTM4XHViMmU0LjxcL3A+XHJcblxyXG48cD50ZXh0LW1vZGUgd2luZG93c1x1Yzc1OCBzY3JlZW4tc2hvdFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWI0NTAgXHVhYzFjXHVjNzU4IHdpbmRvd1x1YjNjNCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgJnF1b3Q7Y2FzY2FkZSBtb2RlJnF1b3Q7XHViODVjIHdpbmRvd1x1Yjk3YyBcdWM4MTVcdWI5YWNcdWQ1NzQgXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIHdpbmRvd1x1Yzc1OCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzBcdWIyOTQgXHViY2MwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCB3aW5kb3dcdWI0ZTRcdWM3NDAgdGl0bGVcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCB3aW5kb3dcdWI0ZTRcdWM3NDQgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVkNjU0XHViYTc0IFx1YzgwNFx1Y2NiNFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjNjJlXHVhZTM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMDk4XHVjMTFjLCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1Y2U3OFx1YzUyOSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHViODVjIFx1YjBiNFx1YjgyNCBcdWJjMzBcdWNlNThcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmE0XHVkMDZjXHViOWIwXHVjNzU4IFx1YzEzOFx1Yjg1YyBcdWFlMzhcdWM3NzQgTVx1YWNmYyBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMTAmbGU7TSwgTiZsZTsxMDApIFx1Yzc3NFx1YzViNFx1YzExYyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgTlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgc2NyZWVuLXNob3RcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0IFx1YzhmY1x1YjI5NCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuIFx1YmMzMFx1YWNiZCBcdWFkZjhcdWI5YmMgXHVhYzE5XHVjNzQwIFx1YWM4M1x1Yzc0MCBcdWM1YzZcdWFjZTAgXHViYWE4XHViNDUwICZsc3F1bzsuJnJzcXVvO1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWJhNzAsIFx1YmFhOFx1YjRlMCB3aW5kb3dcdWM3NTggdGl0bGVcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gTVx1YWNmYyBOXHVjNzQwICZxdW90O2Nhc2NhZGUgbW9kZSZxdW90O1x1Yjg1YyB3aW5kb3dcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgxNVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YjljY1x1ZDA3YyBcdWNkYTlcdWJkODRcdWQ3ODggXHVkMDZjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+TVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwICZxdW90O2Nhc2NhZGUgbW9kZSZxdW90O1x1Yjg1YyB3aW5kb3dcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgxNVx1YjlhY1x1ZDU1YyBcdWQ2NTRcdWJhNzRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJrYXNrYWRlIiwiZGVzY3JpcHRpb24iOiI8cD5BIG51bWJlciBvZiB3aW5kb3dzIGFyZSBkaXNwbGF5ZWQgb24gdGhlIHRleHQtbW9kZSBzY3JlZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSB3aW5kb3cgY29uc2lzdHMgb2YgdGhlIGJvcmRlciByZXByZXNlbnRlZCBieSB0aGUgY2hhcmFjdGVycyAmIzM5Oy0mIzM5OyAobWludXMpLCAmIzM5O3wmIzM5OyAodmVydGljYWwgbGluZSkgYW5kICYjMzk7KyYjMzk7IChwbHVzKSwgb2YgdGhlIGludGVyaW9yIHJlcHJlc2VudGVkIGJ5IHRoZSBjaGFyYWN0ZXJzICYjMzk7LiYjMzk7IChkb3QpLCBhbmQgdGhlIHRpdGxlIG9mIHRoZSB3aW5kb3cgdGhhdCBpcyBsb2NhdGVkIGluIHRoZSBtaWRkbGUgb2YgdGhlIHVwcGVyIGJvcmRlci4gVGhlIHRpdGxlIGlzIGNlbnRlcmVkIG9yIGEgbGl0dGxlIHRvIHRoZSBsZWZ0IGlmIGV4YWN0IGNlbnRlcmluZyBpcyBpbXBvc3NpYmxlLiBNb3JlIHByZWNpc2VseSwgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIGZpcnN0IGxldHRlciBvZiB0aGUgdGl0bGUgYW5kIGxlZnQgYm9yZGVyIHdpbGwgYmUgZXF1YWwgdG8gb3Igb25lIGxlc3MgdGhhbiB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgbGFzdCBsZXR0ZXIgYW5kIHRoZSByaWdodCBib3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggd2luZG93IGlzIHdpZGUgZW5vdWdoIHRvIGNvbnRhaW4gdGhlIHRpdGxlLCB0b2dldGhlciB3aXRoIHRoZSBhZGphY2VudCBzdHJpbmdzICYjMzk7LXwmIzM5OyBvbiB0aGUgbGVmdCwgYW5kICYjMzk7fC0mIzM5OyBvbiB0aGUgcmlnaHQgKG1vcmUgcHJlY2lzZWx5LCB0aGUgd2lkdGggb2YgdGhlIHdpbmRvdyBpcyBhdCBsZWFzdCA2IGNvbHVtbnMgZ3JlYXRlciB0aGFuIHRoZSBsZW5ndGggb2YgdGhlIHRpdGxlKS4gVGhlIGhlaWdodCBvZiBlYWNoIHdpbmRvdyBpcyBhdCBsZWFzdCAzIHJvd3MsIGFuZCBubyB0d28gZGlmZmVyZW50IHdpbmRvd3MgaGF2ZSB0aGUgc2FtZSB0aXRsZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93aW5kb3cucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE1cHg7IHdpZHRoOjE1MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldlIGFyZSBnaXZlbiB0aGUgbGF5b3V0IG9mIGEgc2NyZWVuIHdpdGggYSBudW1iZXIgb2Ygd2luZG93cyBvbiBpdCBzdWNoIHRoYXQgbm8gdHdvIHdpbmRvd3Mgb3ZlcmxhcC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgaGF2ZSB0byBhcnJhbmdlIHRoZSB3aW5kb3dzIGluIHRoZSBzbyBjYWxsZWQgJnF1b3Q7Y2FzY2FkZSBtb2RlJnF1b3Q7IGRlZmluZWQgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiB0aGUgd2luZG93cyBtdXN0IG5vdCBiZSBjaGFuZ2VkJm5ic3A7PFwvbGk+XHJcblx0PGxpPnRoZSB1cHBlciBsZWZ0IGNvcm5lciBvZiB0aGUgZmlyc3Qgd2luZG93IGhhcyB0byBiZSBpbiB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgb2YgdGhlIHNjcmVlbiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5lYWNoIG5leHQgd2luZG93IHNob3VsZCBvdmVybGFwIHdpdGggdGhlIHByZXZpb3VzIG9uZSBhbmQgaXRzIHVwcGVyIGxlZnQgY29ybmVyIGhhcyB0byBiZSBzaGlmdGVkIGV4YWN0bHkgb25lIHJvdyBkb3duIGFuZCBvbmUgY29sdW1uIHJpZ2h0PFwvbGk+XHJcblx0PGxpPndpbmRvd3Mgc2hvdWxkIGJlIGFscGhhYmV0aWNhbGx5IHNvcnRlZCBieSB0aXRsZSAmbmRhc2g7IHRoZSBmaXJzdCB3aW5kb3cgaW4gdGhlIGZpcnN0IHJvdywgdGhlIHNlY29uZCB3aW5kb3cgaW4gdGhlIHNlY29uZCByb3cgZXRjLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTSBhbmQgTiwgMTAgJmxlOyBNLE4gJmxlOyAxMDAsIHRoZSBudW1iZXJzIG9mIHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIHNjcmVlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgTiBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyB0aGUgbGF5b3V0IG9uIHRoZSBzY3JlZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBsZW5ndGggb2YgdGhlIHRpdGxlIG9mIGVhY2ggd2luZG93IHdpbGwgYmUgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxMCBjaGFyYWN0ZXJzLiBUaGUgb25seSBjaGFyYWN0ZXJzIHRoYXQgYXJlIGFsbG93ZWQgYXJlIGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0ICgmIzM5O2EmIzM5Oy0mIzM5O3omIzM5OykuIFRoZSBudW1iZXJzIE0gYW5kIE4gd2lsbCBiZSBsYXJnZSBlbm91Z2ggdGhhdCBhbGwgb2YgdGhlIHdpbmRvd3MsIGFmdGVyIHRoZSByZWFycmFuZ2luZywgY29tcGxldGVseSBmaXQgb250byB0aGUgc2NyZWVuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gTSBsaW5lcyB3aXRoIE4gY2hhcmFjdGVycyBlYWNoICZuZGFzaDsgdGhlIGxheW91dCBvZiB0aGUgc2NyZWVuIGFmdGVyIHRoZSB3aW5kb3dzIGFyZSByZWFycmFuZ2VkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==