给你一个字符串s，你可以进行一种操作：选取前i个字母，得到一个前缀，把它翻转。你可以操作任意次，要求你最后得到的字符串是最小的。

当然，为了增加趣味性，我们有一个限制：你依次取的前缀的长度一定要是递增的。

比如：s="BCDAF"，你可以先把前3个翻转，得到"DCBAF"，然后把前4个翻转，得到"ABCDF"。

输入格式

第一行为一个字符串s

输出格式

你得到的最小字符串。

输入/输出例子1

输入：

ABBA

输出：

AABB

输入/输出例子2

输入：

ACAB

输出：

AACB

样例解释

s的长度在1到50之间。