题目描述

给出小写字母构成的字符串 S ，初始时有一个空字符串 T ，你需要执行以下操作恰好 |S| 次：

选择当前字符串 S 的第一个字符或最后一个字符，将其删去，并添加到 T 字符串的末尾。

请你构造出可以得到的字典序最小的字符串 T 。

输入格式

一行，给出一个字符串 S 。

输出格式

输出一行，表示字符串 T 。

样例

样例输入

acdbcb                                   

样例输出

abcbcd