시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 77 23 19 31.667%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력

6
A
C
D
B
C
B

예제 출력

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"