定义一个字符串是好串，当且仅当它本身是它的最小表示，即字符串 $ 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分）：无特殊限制。