← 返回题目列表

Codeforces · 797/C

C. 最小字符串

中文机器翻译题面 查看原题

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