304162: CF797C. Minimal string

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: