CF797C 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

Print resulting string $ u $ .