F. Card Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Z is playing a card game. He has $$$N$$$ cards stacked face-up in a pile. Each card has a single uppercase letter printed on its face.

The game requires him to rearrange the cards into a new pile, such that the sequence of letters from top to bottom of the new pile is lexicographically smallest.

Each time, Little Z can only take a card from either the top or the bottom of the current pile, and place it onto the bottom of the new pile. This operation is repeated until all cards have been moved to the new pile.

Given the initial sequence of letters from top to bottom, help Little Z find the lexicographically smallest sequence he can obtain.

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 5 \times 10^5$$$).

The following $$$N$$$ lines each contain a single uppercase letter, representing the letters on the cards from top to bottom in the initial pile.

Output

Output a string of length $$$N$$$, representing the lexicographically smallest sequence that can be obtained.

Example
Input
6
B
C
B
D
C
A
Output
ABCBCD
Note

A string $$$s$$$ is lexicographically smaller than a string $$$t$$$ if and only if there exists some index $$$i$$$ such that $$$s_1 = t_1,\ s_2 = t_2,\ \ldots,\ s_{i-1} = t_{i-1}$$$, and $$$s_i \lt t_i$$$; or $$$s$$$ is a proper prefix of $$$t$$$. Characters are compared according to alphabetical order, i.e. $$$\texttt{A} \lt \texttt{B} \lt \cdots \lt \texttt{Z}$$$.

For example, $$$\texttt{AABC} \lt \texttt{ABCA}$$$, since at the second position $$$\texttt{A} \lt \texttt{B}$$$.