Description

Farmer John plans to bring $N$ ( $1 \leq N \leq 5 \times 10^5$ ) cows to the annual "All-American Farmers Grand Prix". In this contest, each participant must line up his cows in a single row, then lead them past the judges one by one.

This year, during registration, the committee adopted a new rule: take the first letter of each cow’s name, in the order they appear in the line, to form a string. Sort all teams’ strings in ascending lexicographic order to determine the order of appearance.

Since FJ is busy, he wants to appear as early as possible. Therefore, he decides to rearrange the line.

His operation is as follows: at each step, he takes one cow from either the front or the back of the original line and appends her to the end of a new line. He repeats this until all cows have been placed into the new line.

Please help FJ compute the lexicographically smallest line that can be formed using the method above.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain a single uppercase letter, representing the initial line.

Output Format

Output a string of length $N$ representing the lexicographically smallest possible line.

Print a newline after every $80$ letters.

6
A
C
D
B
C
B

ABCBCD

Hint

Translated by ChatGPT 5