시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 58 27 20 47.619%

문제

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

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

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

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

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

입력

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 30,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"
W3sicHJvYmxlbV9pZCI6IjYxNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjMGRkXHVjMTMxIDIiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1YyBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYjM4XHVjNzkwXHVjNWY0IFRcdWI5N2MgXHViOWNjXHViNGU0XHViODI0XHVhY2UwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yjg1YyBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhZGRjXHVjZTU5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYjM4XHVjNzkwXHVjNWY0IFNcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzU1ZVx1Yzc1OCBcdWJiMzhcdWM3OTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YmIzOFx1Yzc5MFx1YzVmNCBUXHVjNzU4IFx1YjljOFx1YzljMFx1YjljOVx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWI0YTRcdWM3NTggXHViYjM4XHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgXHVjZDk0XHVhYzAwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNCBcdWFkZGNcdWNlNTlcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBUXHViNGU0IFx1YzkxMSBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChOICZsdDs9IDMwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFNcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIDgwXHVhZTAwXHVjNzkwXHViOWM4XHViMmU0IFx1YzBjOFx1YzkwNCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPG9sPlxyXG5cdDxsaT5TPSZxdW90O0FDREJDQiZxdW90OywgVD0mcXVvdDsmcXVvdDs8XC9saT5cclxuXHQ8bGk+Uz0mcXVvdDtDREJDQiZxdW90OywgVD0mcXVvdDtBJnF1b3Q7PFwvbGk+XHJcblx0PGxpPlM9JnF1b3Q7Q0RCQyZxdW90OywgVD0mcXVvdDtBQiZxdW90OzxcL2xpPlxyXG5cdDxsaT5TPSZxdW90O0NEQiZxdW90OywgVD0mcXVvdDtBQkMmcXVvdDs8XC9saT5cclxuXHQ8bGk+Uz0mcXVvdDtDRCZxdW90OywgVD0mcXVvdDtBQkNCJnF1b3Q7PFwvbGk+XHJcblx0PGxpPlM9JnF1b3Q7RCZxdW90OywgVD0mcXVvdDtBQkNCQyZxdW90OzxcL2xpPlxyXG5cdDxsaT5TPSZxdW90OyZxdW90OywgVD0mcXVvdDtBQkNCQ0QmcXVvdDs8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjE0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgQ293IExpbmUsIEdvbGQiLCJkZXNjcmlwdGlvbiI6IjxwPkZKIGlzIGFib3V0IHRvIHRha2UgaGlzIE4gKDEgJmx0Oz0gTiAmbHQ7PSAzMCwwMDApIGNvd3MgdG8gdGhlIGFubnVhbCAmcXVvdDtGYXJtZXIgb2YgdGhlIFllYXImcXVvdDsgY29tcGV0aXRpb24uIEluIHRoaXMgY29udGVzdCBldmVyeSBmYXJtZXIgYXJyYW5nZXMgaGlzIGNvd3MgaW4gYSBsaW5lIGFuZCBoZXJkcyB0aGVtIHBhc3QgdGhlIGp1ZGdlcy48XC9wPlxyXG5cclxuPHA+VGhlIGNvbnRlc3Qgb3JnYW5pemVycyBhZG9wdGVkIGEgbmV3IHJlZ2lzdHJhdGlvbiBzY2hlbWUgdGhpcyB5ZWFyOiBzaW1wbHkgcmVnaXN0ZXIgdGhlIGluaXRpYWwgbGV0dGVyIG9mIGV2ZXJ5IGNvdyBpbiB0aGUgb3JkZXIgdGhleSB3aWxsIGFwcGVhciAoZS5nLiwgSWYgRkogdGFrZXMgQmVzc2llLCBTeWx2aWEsIGFuZCBEb3JhIGluIHRoYXQgb3JkZXIsIGhlIGp1c3QgcmVnaXN0ZXJzIEJTRCkuIEFmdGVyIHRoZSByZWdpc3RyYXRpb24gcGhhc2UgZW5kcywgZXZlcnkgZ3JvdXAgaXMganVkZ2VkIGluIGluY3JlYXNpbmcgbGV4aWNvZ3JhcGhpYyBvcmRlciAoaS5lLiwgYWxwaGFiZXRpY2FsIG9yZGVyKSBhY2NvcmRpbmcgdG8gdGhlIHN0cmluZyBvZiB0aGUgaW5pdGlhbHMgb2YgdGhlIGNvd3MmIzM5OyBuYW1lcy48XC9wPlxyXG5cclxuPHA+RkogaXMgdmVyeSBidXN5IHRoaXMgeWVhciBhbmQgaGFzIHRvIGh1cnJ5IGJhY2sgdG8gaGlzIGZhcm0sIHNvIGhlIHdhbnRzIHRvIGJlIGp1ZGdlZCBhcyBlYXJseSBhcyBwb3NzaWJsZS4gSGUgZGVjaWRlcyB0byByZWFycmFuZ2UgaGlzIGNvd3MsIHdobyBoYXZlIGFscmVhZHkgbGluZWQgdXAsIGJlZm9yZSByZWdpc3RlcmluZyB0aGVtLjxcL3A+XHJcblxyXG48cD5GSiBtYXJrcyBhIGxvY2F0aW9uIGZvciBhIG5ldyBsaW5lIG9mIHRoZSBjb21wZXRpbmcgY293cy4gSGUgdGhlbiBwcm9jZWVkcyB0byBtYXJzaGFsIHRoZSBjb3dzIGZyb20gdGhlIG9sZCBsaW5lIHRvIHRoZSBuZXcgb25lIGJ5IHJlcGVhdGVkbHkgc2VuZGluZyBlaXRoZXIgdGhlIGZpcnN0IG9yIGxhc3QgY293IGluIHRoZSAocmVtYWluZGVyIG9mIHRoZSkgb3JpZ2luYWwgbGluZSB0byB0aGUgZW5kIG9mIHRoZSBuZXcgbGluZS4gV2hlbiBoZSYjMzk7cyBmaW5pc2hlZCwgRkogdGFrZXMgaGlzIGNvd3MgZm9yIHJlZ2lzdHJhdGlvbiBpbiB0aGlzIG5ldyBvcmRlci48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGluaXRpYWwgb3JkZXIgb2YgaGlzIGNvd3MsIGRldGVybWluZSB0aGUgbGVhc3QgbGV4aWNvZ3JhcGhpYyBzdHJpbmcgb2YgaW5pdGlhbHMgaGUgY2FuIG1ha2UgdGhpcyB3YXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGluaXRpYWwgKCYjMzk7QSYjMzk7Li4mIzM5O1omIzM5Oykgb2YgdGhlIGNvdyBpbiB0aGUgaXRoIHBvc2l0aW9uIGluIHRoZSBvcmlnaW5hbCBsaW5lPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5UaGUgbGVhc3QgbGV4aWNvZ3JhcGhpYyBzdHJpbmcgaGUgY2FuIG1ha2UuIEV2ZXJ5IGxpbmUgKGV4Y2VwdCBwZXJoYXBzIHRoZSBsYXN0IG9uZSkgY29udGFpbnMgdGhlIGluaXRpYWxzIG9mIDgwIGNvd3MgKCYjMzk7QSYjMzk7Li4mIzM5O1omIzM5OykgaW4gdGhlIG5ldyBsaW5lLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cHJlPlxyXG4gIFN0ZXAgICBPcmlnaW5hbCAgICAgTmV3XHJcbiAgICMxICAgICBBQ0RCQ0JcclxuICAgIzIgICAgICBDREJDQiAgICAgQVxyXG4gICAjMyAgICAgIENEQkMgICAgICBBQlxyXG4gICAjNCAgICAgIENEQiAgICAgICBBQkNcclxuICAgIzUgICAgICBDRCAgICAgICAgQUJDQlxyXG4gICAjNiAgICAgICBEICAgICAgICBBQkNCQ1xyXG4gICAjNyAgICAgICAgICAgICAgICBBQkNCQ0Q8XC9wcmU+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==