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 $ .

输入输出样例

输入样例 #1

cab

输出样例 #1

abc

输入样例 #2

acdb

输出样例 #2

abdc