A string is defined as a "good string" if and only if it is its own minimal representation. That is, a string $s = s_1s_2\cdots s_n$ is a good string if and only if for all $2 \leq i \leq n$, the string $t = s_is_{i+1}s_{i+2}\cdots s_ns_1s_2\cdots s_{i-1}$ is lexicographically greater than or equal to $s$.

Given a string $S$ consisting only of lowercase letters, rearrange the letters in $S$ to form a good string such that the lexicographical order of this string is maximized. Output the rearranged string.

Input

A single line containing the string $S$.

Output

A single line containing the string representing the answer.

Examples

Input 1

acbca

Output 1

acacb

Input 2

cadcbaadcbadbacdb

Output 2

accccbbbbadadadad

Constraints

For all test cases, it is guaranteed that $1 \leq |S| \leq 10^6$. The special constraints for each subtask are as follows:

• Subtask 1 (10 points): $|S| \leq 10$
• Subtask 2 (20 points): $|S| \leq 50, S_i \in \{\texttt{a}, \texttt{b}, \texttt{c}\}$
• Subtask 3 (30 points): $|S| \leq 1000$
• Subtask 4 (40 points): No additional constraints.