Minimal string
题目描述
C. Minimal string
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputPetya 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.
Input
First line contains non-empty string s (1≤|s|≤105), consisting of lowercase English letters.
Output
Print resulting string u.
Examples
Input
cab
Output
abc
Input
acdb
Output
abdc
题目来源：fps-www.educg.net-codeforce-1-2833.xml.zip；FPS 共享题包，题包内第 235 题。保留原作者与原赛事署名。