600128 : 字符和栈
描述

给一个字符串,依次将其中字符入栈,输出字典序最小的出栈序列。

你可以在任何时候选择出栈任意多个字符,只要栈中还有字符可以出栈。

输入

一行,一个仅小写英文字母(a-z)构成的字符串,长度不超过10^5。

输出

一个长度相同的字符串,表示字典序最小的出栈结果。

样例

输入

cab

输出

abc

输入

acdb

输出

abdc

输入

iakz

输出

aikz
语言:
主题: