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