문자열 생성

길이가 $N$인 문자열 $S$가 주어진다.

문자열 $S$의 문자들을 사용하여 새로운 문자열 $T$를 만든다. 처음에 $T$는 빈 문자열이며, $S$가 빈 문자열이 될 때까지 다음 두 연산 중 하나를 반복한다.

• $S$의 맨 앞 문자를 하나 꺼내어 $T$의 맨 뒤에 붙인다.
• $S$의 맨 뒤 문자를 하나 꺼내어 $T$의 맨 뒤에 붙인다.

이렇게 만들 수 있는 모든 문자열 $T$ 중에서 사전순으로 가장 앞서는 것을 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 $S$의 길이 $N$이 주어진다. ($1 \le N \le 2,000$)

이어지는 $N$개의 줄에 $S$를 이루는 문자가 한 줄에 하나씩 순서대로 주어진다.

만들 수 있는 문자열 $T$ 중 사전순으로 가장 앞서는 것을 출력한다. 이때 80글자마다 줄을 바꾸어 출력한다.

$S = $ ACDBCB에서 시작하여 $T$를 만들어 가는 과정의 한 예는 다음과 같다.