Score : $400$ points

Problem Statement

Given is a string $s$ of length $N$. Let $s_i$ denote the $i$-th character of $s$.

Snuke will transform $s$ by the following procedure.

• Choose an even length (not necessarily contiguous) subsequence $x=(x_1, x_2, \ldots, x_{2k})$ of $(1,2, \ldots, N)$ ($k$ may be $0$).
• Swap $s_{x_1}$ and $s_{x_{2k}}$.
• Swap $s_{x_2}$ and $s_{x_{2k-1}}$.
• Swap $s_{x_3}$ and $s_{x_{2k-2}}$.
• $\vdots$
• Swap $s_{x_{k}}$ and $s_{x_{k+1}}$.

Among the strings that $s$ can become after the procedure, find the lexicographically smallest one.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $s$ is a string of length $N$ consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$N$

$s$

Output

Print the lexicographically smallest possible string $s$ after the procedure by Snuke.

4
dcab

acdb

• When $x=(1,3)$, the procedure just swaps $s_{1}$ and $s_{3}$.
• The $s$ after the procedure is acdb, the lexicographically smallest possible result.

2
ab

ab

• When $x=()$, the $s$ after the procedure is ab, the lexicographically smallest possible result.
• Note that $x$ may have a length of $0$.

16
cabaaabbbabcbaba

aaaaaaabbbbcbbbc

17
snwfpfwipeusiwkzo

effwpnwipsusiwkzo