시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 172 64 47 37.008%

문제

N개의 문자로 이루어진 문자열 S가 입력된다.

이 문자열의 각 문자들로 새로운 문자열 T를 만들려고한다.

문자열 S로 문자열 T를 만드는 규칙은 다음과 같다.

  • 문자열 S의 가장 앞의 문자 하나를 문자열 T의 마지막에 추가한다.
  • 문자열 S의 가장 뒤의 문자 하나를 문자열 T의 마지막에 추가한다.

위 규칙으로 만들어진 문자열 T들 중 사전순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000)

이후 N개의 줄에 S를 이루는 문자들이 주어진다.

출력

만들어진 사전순으로 가장 빠른 문자열을 출력한다. 80글자마다 새줄 문자를 출력해야 한다.

예제 입력 1

6
A
C
D
B
C
B

예제 출력 1

ABCBCD

힌트

  1. S="ACDBCB", T=""
  2. S="CDBCB", T="A"
  3. S="CDBC", T="AB"
  4. S="CDB", T="ABC"
  5. S="CD", T="ABCB"
  6. S="D", T="ABCBC"
  7. S="", T="ABCBCD"
W3sicHJvYmxlbV9pZCI6IjYxMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjMGRkXHVjMTMxIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMwMSBcdWJiMzhcdWM3OTBcdWI0ZTRcdWI4NWMgXHVjMGM4XHViODVjXHVjNmI0IFx1YmIzOFx1Yzc5MFx1YzVmNCBUXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0IFNcdWI4NWMgXHViYjM4XHVjNzkwXHVjNWY0IFRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM3NTggXHViYjM4XHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgXHVjZDk0XHVhYzAwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHViNGE0XHVjNzU4IFx1YmIzOFx1Yzc5MCBcdWQ1NThcdWIwOThcdWI5N2MgXHViYjM4XHVjNzkwXHVjNWY0IFRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3MDQgXHVhZGRjXHVjZTU5XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1YjRlNCBcdWM5MTEgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoTiAmbHQ7PSAyLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFNcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIDgwXHVhZTAwXHVjNzkwXHViOWM4XHViMmU0IFx1YzBjOFx1YzkwNCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPG9sPlxyXG5cdDxsaT5TPSZxdW90O0FDREJDQiZxdW90OywgVD0mcXVvdDsmcXVvdDs8XC9saT5cclxuXHQ8bGk+Uz0mcXVvdDtDREJDQiZxdW90OywgVD0mcXVvdDtBJnF1b3Q7PFwvbGk+XHJcblx0PGxpPlM9JnF1b3Q7Q0RCQyZxdW90OywgVD0mcXVvdDtBQiZxdW90OzxcL2xpPlxyXG5cdDxsaT5TPSZxdW90O0NEQiZxdW90OywgVD0mcXVvdDtBQkMmcXVvdDs8XC9saT5cclxuXHQ8bGk+Uz0mcXVvdDtDRCZxdW90OywgVD0mcXVvdDtBQkNCJnF1b3Q7PFwvbGk+XHJcblx0PGxpPlM9JnF1b3Q7RCZxdW90OywgVD0mcXVvdDtBQkNCQyZxdW90OzxcL2xpPlxyXG5cdDxsaT5TPSZxdW90OyZxdW90OywgVD0mcXVvdDtBQkNCQ0QmcXVvdDs8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjEzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgQ293IExpbmUiLCJkZXNjcmlwdGlvbiI6IjxwPkZKIGlzIGFib3V0IHRvIHRha2UgaGlzIE4gKDEgJmx0Oz0gTiAmbHQ7PSAyLDAwMCkgY293cyB0byB0aGUgYW5udWFsICZxdW90O0Zhcm1lciBvZiB0aGUgWWVhciZxdW90OyBjb21wZXRpdGlvbi4gSW4gdGhpcyBjb250ZXN0IGV2ZXJ5IGZhcm1lciBhcnJhbmdlcyBoaXMgY293cyBpbiBhIGxpbmUgYW5kIGhlcmRzIHRoZW0gcGFzdCB0aGUganVkZ2VzLjxcL3A+XHJcblxyXG48cD5UaGUgY29udGVzdCBvcmdhbml6ZXJzIGFkb3B0ZWQgYSBuZXcgcmVnaXN0cmF0aW9uIHNjaGVtZSB0aGlzIHllYXI6IHNpbXBseSByZWdpc3RlciB0aGUgaW5pdGlhbCBsZXR0ZXIgb2YgZXZlcnkgY293IGluIHRoZSBvcmRlciB0aGV5IHdpbGwgYXBwZWFyIChpLmUuLCBJZiBGSiB0YWtlcyBCZXNzaWUsIFN5bHZpYSwgYW5kIERvcmEgaW4gdGhhdCBvcmRlciBoZSBqdXN0IHJlZ2lzdGVycyBCU0QpLiBBZnRlciB0aGUgcmVnaXN0cmF0aW9uIHBoYXNlIGVuZHMsIGV2ZXJ5IGdyb3VwIGlzIGp1ZGdlZCBpbiBpbmNyZWFzaW5nIGxleGljb2dyYXBoaWMgb3JkZXIgYWNjb3JkaW5nIHRvIHRoZSBzdHJpbmcgb2YgdGhlIGluaXRpYWxzIG9mIHRoZSBjb3dzJiMzOTsgbmFtZXMuPFwvcD5cclxuXHJcbjxwPkZKIGlzIHZlcnkgYnVzeSB0aGlzIHllYXIgYW5kIGhhcyB0byBodXJyeSBiYWNrIHRvIGhpcyBmYXJtLCBzbyBoZSB3YW50cyB0byBiZSBqdWRnZWQgYXMgZWFybHkgYXMgcG9zc2libGUuIEhlIGRlY2lkZXMgdG8gcmVhcnJhbmdlIGhpcyBjb3dzLCB3aG8gaGF2ZSBhbHJlYWR5IGxpbmVkIHVwLCBiZWZvcmUgcmVnaXN0ZXJpbmcgdGhlbS48XC9wPlxyXG5cclxuPHA+RkogbWFya3MgYSBsb2NhdGlvbiBmb3IgYSBuZXcgbGluZSBvZiB0aGUgY29tcGV0aW5nIGNvd3MuIEhlIHRoZW4gcHJvY2VlZHMgdG8gbWFyc2hhbCB0aGUgY293cyBmcm9tIHRoZSBvbGQgbGluZSB0byB0aGUgbmV3IG9uZSBieSByZXBlYXRlZGx5IHNlbmRpbmcgZWl0aGVyIHRoZSBmaXJzdCBvciBsYXN0IGNvdyBpbiB0aGUgKHJlbWFpbmRlciBvZiB0aGUpIG9yaWdpbmFsIGxpbmUgdG8gdGhlIGVuZCBvZiB0aGUgbmV3IGxpbmUuIFdoZW4gaGUmIzM5O3MgZmluaXNoZWQsIEZKIHRha2VzIGhpcyBjb3dzIGZvciByZWdpc3RyYXRpb24gaW4gdGhpcyBuZXcgb3JkZXIuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBpbml0aWFsIG9yZGVyIG9mIGhpcyBjb3dzLCBkZXRlcm1pbmUgdGhlIGxlYXN0IGxleGljb2dyYXBoaWMgc3RyaW5nIG9mIGluaXRpYWxzIGhlIGNhbiBtYWtlIHRoaXMgd2F5LjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbml0aWFsICgmIzM5O0EmIzM5Oy4uJiMzOTtaJiMzOTspIG9mIHRoZSBjb3cgaW4gdGhlIGl0aCBwb3NpdGlvbiBpbiB0aGUgb3JpZ2luYWwgbGluZTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGxlYXN0IGxleGljb2dyYXBoaWMgc3RyaW5nIGhlIGNhbiBtYWtlLiBFdmVyeSBsaW5lIChleGNlcHQgcGVyaGFwcyB0aGUgbGFzdCBvbmUpIGNvbnRhaW5zIHRoZSBpbml0aWFscyBvZiA4MCBjb3dzICgmIzM5O0EmIzM5Oy4uJiMzOTtaJiMzOTspIGluIHRoZSBuZXcgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=