Minimal string

给出一个字符串，按照从前到后的顺序进栈，输出字典序最小的出栈序列

Petya recieved a gift of a string $ s $ with length up to $ 10^{5} $ 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.

First line contains non-empty string $ s $ ( $ 1<=|s|<=10^{5} $ ), consisting of lowercase English letters.

Print resulting string $ u $ .

cab

abc

acdb

abdc