Petya 收到了一份生日礼物,即长度最多 105 个字符的字符串 s。他又拿了两根空弦t和u,决定玩一个游戏。这个游戏有两种可能的动作:
- 提取 s 的第一个字符并将该字符附加到 t 后面。
- 提取 t 的最后一个字符并将该字符附加到 u 上。
Petya 希望将字符串 s 和 t 设为空,并将字符串 u 按字典顺序最小化。
你应该编写一个程序来帮助 Petya 赢得比赛。
输入
第一行包含非空字符串 s (1 ≤ |s| ≤ 105),由小写英文字母组成。
输出
打印结果字符串 u。
示例
输入 #1
cab
输出 #1
abc
输入 #2
acdb
输出 #2
abdc