CF797C.Minimal string

Petya recieved a gift of a string s with length up to 105 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:

• Extract the first character of s and append t with this character.
• Extract the last character of t and append u with this character.

Petya wants to get strings s and t empty and string u lexicographically minimal.

You should write a program that will help Petya win the game.

佩佳生日时收到了一份礼物：一个长度最多为 $10^5$ 的字符串 $s$。他另外准备了两个空字符串 $t$ 和 $u$，并决定玩一个游戏。该游戏有两种可能的操作：

• 取出 $s$ 的第一个字符，并将其追加到 $t$ 的末尾；
• 取出 $t$ 的最后一个字符，并将其追加到 $u$ 的末尾。

佩佳希望最终使字符串 $s$ 和 $t$ 均为空，且字符串 $u$ 的字典序尽可能小。

你需要编写一个程序，帮助佩佳赢得这个游戏。

First line contains non-empty string s (1 ≤ |s| ≤ 105), consisting of lowercase English letters.

第一行包含一个非空字符串 $s$（$1 \leq |s| \leq 10^5$），由小写英文字母组成。

Print resulting string u.

输出结果字符串 $u$。