QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
Statistics

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