背景描述：
“Hi，Will! 能帮我个忙么？”一个甜美的声音传来。
Will一抬头才发现，哇塞！是MM呀！MM主动和Will打招呼啊！Will心中不禁涌起如长江黄河般的澎湃波涛！Will下定决心：“MM的这个忙，一定得帮！”。
“Will，WW和我玩翻转游戏，她总是赢我……”下面的话不说Will也知道，谁让MM比WW漂亮不止一点两点呢，漂亮的人，总是有点虚荣心得嘛！
不过，考虑到Will正在Fifa中，所以他就要请你帮忙啦！
翻转游戏是一个基于字符串上的游戏，给一个由大写字母组成字符串，按照上升序列考察每个i（1≤i≤字符串长度 ），对于每个i，你可以选择是否将当前字符串前i个字母翻转，所有操作完毕后，得到的串字典序小的一方就获胜。
为了在MM面前表现一下，Will的要求是：只求最好，不求更好 :D

问题：
输入由大写字母组成的字符串 S，按上述规则以长度上升序列考察前缀，求可得到的字典序最小的串。

输入：
第一行，一个字符串 S

输出：
一行，一个字符串，即所给数据的答案。

样例1：
[reverse.in]
BCDAF

[reverse.out]
ABCDF

样例2：
[reverse.in]
ABBA

[reverse.out]
AABB

样例3：
[reverse.in]
ACAB

[reverse.out]
AACB

Hint:
对于串 ABBA，我们选择操作的i是 3 和 4
I = 3
ABBA BBAA
I = 4
BBAA AABB
以上结果是最优的了。

数据规模：
对于40%的数据 length(S) ≤ 10
对于另外20%的数据 S 由 ‘A’ 和 ‘B’ 组成
对于另外20%的数据 S 由 ‘A’, ‘B’ 和 ‘C’ 组成
对于100%的数据 length(S) ≤ 500