문자열 생성 2

$N$개의 문자로 이루어진 문자열 $S$가 주어진다. 이 문자열을 이루는 문자들을 사용하여 새로운 문자열 $T$를 만들려고 한다.

$T$는 $S$가 빌 때까지 다음 두 가지 연산 중 하나를 반복하여 만든다.

• $S$의 맨 앞(왼쪽 끝) 문자 하나를 꺼내 $T$의 맨 뒤에 붙인다.
• $S$의 맨 뒤(오른쪽 끝) 문자 하나를 꺼내 $T$의 맨 뒤에 붙인다.

즉, 매 단계마다 아직 남아 있는 $S$의 맨 앞 또는 맨 뒤에서 문자 하나를 골라 $T$의 끝에 이어 붙인다. 이렇게 만들 수 있는 모든 $T$ 중에서 사전순으로 가장 앞서는(가장 작은) 문자열을 출력하는 프로그램을 작성하시오.

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

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

만들 수 있는 문자열 중 사전순으로 가장 작은 문자열 $T$를 출력한다.

단, 한 줄에 최대 80글자씩 출력한다. 즉 80글자를 출력할 때마다 줄을 바꾼다.

예를 들어 $S=$ ACDBCB인 경우를 살펴보자. 매 단계에서 남아 있는 $S$의 맨 앞 문자와 맨 뒤 문자를 비교하여, 더 작은 문자열을 만드는 쪽의 문자를 $T$에 붙인다. 두 문자가 같으면 안쪽으로 한 글자씩 들어가며 처음으로 달라지는 위치를 비교해 더 작은 쪽 끝을 고른다.

• 맨 앞 A < 맨 뒤 B 이므로 앞의 A를 붙인다. (남은 $S=$ CDBCB, $T=$ A)
• 맨 뒤 B < 맨 앞 C 이므로 뒤의 B를 붙인다. (남은 $S=$ CDBC, $T=$ AB)
• 양 끝이 모두 C이므로 안쪽 D와 B를 비교하면 뒤쪽이 작다. 뒤의 C를 붙인다. (남은 $S=$ CDB, $T=$ ABC)
• 맨 뒤 B < 맨 앞 C 이므로 뒤의 B를 붙인다. (남은 $S=$ CD, $T=$ ABCB)
• 맨 앞 C < 맨 뒤 D 이므로 앞의 C를 붙인다. (남은 $S=$ D, $T=$ ABCBC)
• 남은 문자 D를 붙인다. (남은 $S$ 없음, $T=$ ABCBCD)

따라서 답은 ABCBCD이다.