#37. ctl

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ce-amtic

题目描述

给定一个字符串 S ,可以将其任意划分成若干段连续非空子串的和,即划分为 S=s_1s_2...s_k ,满足 \forall i, s_i\neq\emptyset

可以从 s_1\text{~}s_k 中选出任意多段 s_i ,将其反转,即令 s_i=\text{reverse}(s_i) ;其余的 s_i 保留不变。

求最后得到的 S'=s_1s_2...s_k 字典序最小可能是多少?

输入格式

一行一个字符串 S

输出格式

一行一个字符串,表示字典序最小的 S'

样例

Sample Input

slstxdy

Sample Output

dxtslsy

数据范围与提示

100\% : |S|\le 10^6