定义一个字符串是好串，当且仅当它本身是它的最小表示，即字符串 $s = s_1s_2\cdots s_n$ 是好串当且仅当 $\forall 2 \leq i \leq n$，字符串 $t = s_is_{i+1}s_{i+2}\cdots s_ns_1s_2\cdots s_{i-1}$ 的字典序不小于 $s$。

给定一个仅有小写字母组成的字符串 $S$，将 $S$ 中的字母重新排列成一个好的字符串，并最大化这个字符串的字典序。输出重排后的字符串。

输入格式

输入一行一个字符串 $S$。

输出格式

输出一行一个字符串，表示答案。

样例数据

样例 1输入

acbca

样例 1 输出

acacb

样例 2 输入

cadcbaadcbadbacdb

样例 2 输出

accccbbbbadadadad

数据范围与提示

对于所有数据，保证 $1 \leq |S| \leq 10^6$。每个子任务的特殊限制如下：

Sub 1（10分）：$|S| \leq 10$；

Sub 2（20分）：$|S| \leq 50, S_i \in \{\texttt{a}, \texttt{b}, \texttt{c}\}$；

Sub 3（30分）：$|S| \leq 1000$；

Sub 4（40分）：无特殊限制。