시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3691029329.904%

문제

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

12 12
............
.+-|ana|-+..
.|.......|..
.|.......|..
.|.......|..
.+-------+..
..+-|jozo|-+
..|........|
..|........|
..|........|
..|........|
..+--------+

예제 출력 1

+-|ana|-+...
|+-|jozo|-+.
||........|.
||........|.
+|........|.
.|........|.
.+--------+.
............
............
............
............
............

예제 입력 2

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

예제 출력 2

+-|a|-+...............
|+----|kit|----+......
||+-|winamp|--+|......
|||...........||......
|||...........||......
|||...........||......
|||...........||......
|++-----------++......
|.....|...............
|.....|...............
|.....|...............
|.....|...............
+-----+...............
......................
......................

예제 입력 3

14 15
+---|a|---+....
|.........|....
|.........|....
+---------+....
...............
...............
+--|ab|---+....
|.........|....
|.........|....
+---------+....
+--|abc|--+....
|.........|....
|.........|....
+---------+....

예제 출력 3

+---|a|---+....
|+--|ab|---+...
||+--|abc|--+..
+||.........|..
.+|.........|..
..+---------+..
...............
...............
...............
...............
...............
...............
...............
...............
W3sicHJvYmxlbV9pZCI6IjIwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJ3aW5kb3dzIiwiZGVzY3JpcHRpb24iOiI8cD50ZXh0LW1vZGUgd2luZG93c1x1Yzc1OCBcdWFjMWNcdWJjMWNcdWM3OTBcdWM3NzggXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0ICZxdW90O2Nhc2NhZGUgbW9kZSAoXHVhY2M0XHViMmU4XHVkNjE1IFx1YmMzMFx1Y2U1OCkmcXVvdDsgXHViZDgwXHViZDg0XHVjNzQ0IFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjJlNFx1YWMwMCBcdWFjZTBcdWMyZWNcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiB0ZXh0LW1vZGUgd2luZG93c1x1YzVkMFx1YzExYyBcdWQ1NThcdWIwOThcdWM3NTggd2luZG93XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgJmxzcXVvOysmcnNxdW87LCAmbHNxdW87LSZyc3F1bzssICZsc3F1bzt8JnJzcXVvOywgJmxzcXVvOy4mcnNxdW87LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4rLS18YWJjZGVmfC0tLStcclxufC4uLi4uLi4uLi4uLi58XHJcbnwuLi4uLi4uLi4uLi4ufFxyXG58Li4uLi4uLi4uLi4uLnxcclxufC4uLi4uLi4uLi4uLi58XHJcbistLS0tLS0tLS0tLS0tK1xyXG48XC9wcmU+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgd2luZG93XHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVkMGRjXHViOTdjIFx1YzljMFx1ZDBhNFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIHRpdGxlXHVjNzQ0IFx1YWUzMFx1Yjg1ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YzgxNVx1YjNjNFx1Yjg1YyB3aW5kb3dcdWIyOTQgXHViMTEzXHViMmU0LiAoXHVjOTg5LCB0aXRsZVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHViYWE4XHViNGUwIHdpbmRvd1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgNiBcdWM3NzRcdWMwYzFcdWM3NDAgXHVhYzAwXHViODVjXHViODVjIFx1YWUzOFx1YjJlNC4gKy18LCB8LStcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YykgdGl0bGVcdWM3NDAgXHVhYzAwXHViODVjXHViODVjIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWFjMDBcdWM2YjRcdWIzNzBcdWM1ZDAgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViOWNjXHVjNzdjIFx1YzcwNFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM2NDAgXHVhYzE5XHVjNzc0IHdpbmRvd1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVkNjQwXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzQgXHVjNjdjXHVjYWJkXHViY2Y0XHViMmU0IFx1ZDU1OFx1YjA5OCBcdWIzNTQgXHVhZTM4XHViMmU0LjxcL3A+XHJcblxyXG48cD50ZXh0LW1vZGUgd2luZG93c1x1Yzc1OCBzY3JlZW4tc2hvdFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWI0NTAgXHVhYzFjXHVjNzU4IHdpbmRvd1x1YjNjNCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgJnF1b3Q7Y2FzY2FkZSBtb2RlJnF1b3Q7XHViODVjIHdpbmRvd1x1Yjk3YyBcdWM4MTVcdWI5YWNcdWQ1NzQgXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIHdpbmRvd1x1Yzc1OCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzBcdWIyOTQgXHViY2MwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCB3aW5kb3dcdWI0ZTRcdWM3NDAgdGl0bGVcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCB3aW5kb3dcdWI0ZTRcdWM3NDQgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVkNjU0XHViYTc0IFx1YzgwNFx1Y2NiNFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjNjJlXHVhZTM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMDk4XHVjMTFjLCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1Y2U3OFx1YzUyOSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHViODVjIFx1YjBiNFx1YjgyNCBcdWJjMzBcdWNlNThcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmE0XHVkMDZjXHViOWIwXHVjNzU4IFx1YzEzOFx1Yjg1YyBcdWFlMzhcdWM3NzQgTVx1YWNmYyBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMTAmbGU7TSwgTiZsZTsxMDApIFx1Yzc3NFx1YzViNFx1YzExYyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgTlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgc2NyZWVuLXNob3RcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0IFx1YzhmY1x1YjI5NCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuIFx1YmMzMFx1YWNiZCBcdWFkZjhcdWI5YmMgXHVhYzE5XHVjNzQwIFx1YWM4M1x1Yzc0MCBcdWM1YzZcdWFjZTAgXHViYWE4XHViNDUwICZsc3F1bzsuJnJzcXVvO1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWJhNzAsIFx1YmFhOFx1YjRlMCB3aW5kb3dcdWM3NTggdGl0bGVcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gTVx1YWNmYyBOXHVjNzQwICZxdW90O2Nhc2NhZGUgbW9kZSZxdW90O1x1Yjg1YyB3aW5kb3dcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgxNVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YjljY1x1ZDA3YyBcdWNkYTlcdWJkODRcdWQ3ODggXHVkMDZjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+TVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwICZxdW90O2Nhc2NhZGUgbW9kZSZxdW90O1x1Yjg1YyB3aW5kb3dcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgxNVx1YjlhY1x1ZDU1YyBcdWQ2NTRcdWJhNzRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJrYXNrYWRlIiwiZGVzY3JpcHRpb24iOiI8cD5BIG51bWJlciBvZiB3aW5kb3dzIGFyZSBkaXNwbGF5ZWQgb24gdGhlIHRleHQtbW9kZSBzY3JlZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSB3aW5kb3cgY29uc2lzdHMgb2YgdGhlIGJvcmRlciByZXByZXNlbnRlZCBieSB0aGUgY2hhcmFjdGVycyAmIzM5Oy0mIzM5OyAobWludXMpLCAmIzM5O3wmIzM5OyAodmVydGljYWwgbGluZSkgYW5kICYjMzk7KyYjMzk7IChwbHVzKSwgb2YgdGhlIGludGVyaW9yIHJlcHJlc2VudGVkIGJ5IHRoZSBjaGFyYWN0ZXJzICYjMzk7LiYjMzk7IChkb3QpLCBhbmQgdGhlIHRpdGxlIG9mIHRoZSB3aW5kb3cgdGhhdCBpcyBsb2NhdGVkIGluIHRoZSBtaWRkbGUgb2YgdGhlIHVwcGVyIGJvcmRlci4gVGhlIHRpdGxlIGlzIGNlbnRlcmVkIG9yIGEgbGl0dGxlIHRvIHRoZSBsZWZ0IGlmIGV4YWN0IGNlbnRlcmluZyBpcyBpbXBvc3NpYmxlLiBNb3JlIHByZWNpc2VseSwgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIGZpcnN0IGxldHRlciBvZiB0aGUgdGl0bGUgYW5kIGxlZnQgYm9yZGVyIHdpbGwgYmUgZXF1YWwgdG8gb3Igb25lIGxlc3MgdGhhbiB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgbGFzdCBsZXR0ZXIgYW5kIHRoZSByaWdodCBib3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggd2luZG93IGlzIHdpZGUgZW5vdWdoIHRvIGNvbnRhaW4gdGhlIHRpdGxlLCB0b2dldGhlciB3aXRoIHRoZSBhZGphY2VudCBzdHJpbmdzICYjMzk7LXwmIzM5OyBvbiB0aGUgbGVmdCwgYW5kICYjMzk7fC0mIzM5OyBvbiB0aGUgcmlnaHQgKG1vcmUgcHJlY2lzZWx5LCB0aGUgd2lkdGggb2YgdGhlIHdpbmRvdyBpcyBhdCBsZWFzdCA2IGNvbHVtbnMgZ3JlYXRlciB0aGFuIHRoZSBsZW5ndGggb2YgdGhlIHRpdGxlKS4gVGhlIGhlaWdodCBvZiBlYWNoIHdpbmRvdyBpcyBhdCBsZWFzdCAzIHJvd3MsIGFuZCBubyB0d28gZGlmZmVyZW50IHdpbmRvd3MgaGF2ZSB0aGUgc2FtZSB0aXRsZS48XC9wPlxyXG5cclxuPHByZSBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cclxuKy0tfHdpbmRvd3wtLS0rXHJcbnwuLi4uLi4uLi4uLi4ufFxyXG58Li4uLi4uLi4uLi4uLnxcclxufC4uLi4uLi4uLi4uLi58XHJcbnwuLi4uLi4uLi4uLi4ufFxyXG4rLS0tLS0tLS0tLS0tLSs8XC9wcmU+XHJcblxyXG48cD5XZSBhcmUgZ2l2ZW4gdGhlIGxheW91dCBvZiBhIHNjcmVlbiB3aXRoIGEgbnVtYmVyIG9mIHdpbmRvd3Mgb24gaXQgc3VjaCB0aGF0IG5vIHR3byB3aW5kb3dzIG92ZXJsYXAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGhhdmUgdG8gYXJyYW5nZSB0aGUgd2luZG93cyBpbiB0aGUgc28gY2FsbGVkICZxdW90O2Nhc2NhZGUgbW9kZSZxdW90OyBkZWZpbmVkIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGhlaWdodCBhbmQgd2lkdGggb2YgdGhlIHdpbmRvd3MgbXVzdCBub3QgYmUgY2hhbmdlZCZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgdXBwZXIgbGVmdCBjb3JuZXIgb2YgdGhlIGZpcnN0IHdpbmRvdyBoYXMgdG8gYmUgaW4gdGhlIHVwcGVyIGxlZnQgY29ybmVyIG9mIHRoZSBzY3JlZW4mbmJzcDs8XC9saT5cclxuXHQ8bGk+ZWFjaCBuZXh0IHdpbmRvdyBzaG91bGQgb3ZlcmxhcCB3aXRoIHRoZSBwcmV2aW91cyBvbmUgYW5kIGl0cyB1cHBlciBsZWZ0IGNvcm5lciBoYXMgdG8gYmUgc2hpZnRlZCBleGFjdGx5IG9uZSByb3cgZG93biBhbmQgb25lIGNvbHVtbiByaWdodDxcL2xpPlxyXG5cdDxsaT53aW5kb3dzIHNob3VsZCBiZSBhbHBoYWJldGljYWxseSBzb3J0ZWQgYnkgdGl0bGUgJm5kYXNoOyB0aGUgZmlyc3Qgd2luZG93IGluIHRoZSBmaXJzdCByb3csIHRoZSBzZWNvbmQgd2luZG93IGluIHRoZSBzZWNvbmQgcm93IGV0Yy4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE0gYW5kIE4sIDEwICZsZTsgTSxOICZsZTsgMTAwLCB0aGUgbnVtYmVycyBvZiByb3dzIGFuZCBjb2x1bW5zIG9mIHRoZSBzY3JlZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIE4gY2hhcmFjdGVycyByZXByZXNlbnRpbmcgdGhlIGxheW91dCBvbiB0aGUgc2NyZWVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGVuZ3RoIG9mIHRoZSB0aXRsZSBvZiBlYWNoIHdpbmRvdyB3aWxsIGJlIGF0IGxlYXN0IDEgYW5kIGF0IG1vc3QgMTAgY2hhcmFjdGVycy4gVGhlIG9ubHkgY2hhcmFjdGVycyB0aGF0IGFyZSBhbGxvd2VkIGFyZSBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCAoJiMzOTthJiMzOTstJiMzOTt6JiMzOTspLiBUaGUgbnVtYmVycyBNIGFuZCBOIHdpbGwgYmUgbGFyZ2UgZW5vdWdoIHRoYXQgYWxsIG9mIHRoZSB3aW5kb3dzLCBhZnRlciB0aGUgcmVhcnJhbmdpbmcsIGNvbXBsZXRlbHkgZml0IG9udG8gdGhlIHNjcmVlbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIE0gbGluZXMgd2l0aCBOIGNoYXJhY3RlcnMgZWFjaCAmbmRhc2g7IHRoZSBsYXlvdXQgb2YgdGhlIHNjcmVlbiBhZnRlciB0aGUgd2luZG93cyBhcmUgcmVhcnJhbmdlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d