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