Petya recieved a gift of a string *s* with length up to 10<sup class="upper-index">5</sup> 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<sup class="upper-index">5</sup>), consisting of lowercase English letters.
none
cab
abc
acdb
abdc
a
a
ab
ab
ba
ab
dijee
deeji
bhrmc
bcmrh
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bababaaababaabbbbbabbbbbbaaabbabaaaaabbbbbaaaabbbbabaabaabababbbabbabbabaaababbabbababaaaaabaaaabbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bccbbcccbccbacacbaccaababcbaababaaaaabcaaabcaacbabcaababaabaccacacccbacbcacbbbaacaaccccabbbbacbcbbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbcbcbbbbcccccbbbccbcbccccccbbbcbbccbcbbbbcbbccbccbccbcccbbccb
eejahjfbbcdhbieiigaihidhageiechaadieecaaehcehjbddgcjgagdfgffdaaihbecebdjhjagghecdhbhdfbedhfhfafbjajg
aaaaaaaaaaaaagjjbffhfhdebfdhbhdcehggjhjdbecebhidffgfdggjcgddbjhecheceeidhceieghdihigiieibhdcbbfjhjee
bnrdfnybkzepmluyrhofwnwvfmkdwolvyzrqhuhztvlwjldqmoyxzytpfmrgouymeupxrvpbesyxixnrfbxnqcwgmgjstknqtwrr
bbbbcggjknqrrwttsmwqnxfrnxixysepvrxpuemyuogrmfptyzxyomqdljwlvtzhuhqrzyvlowdkmfvwnwfohryulmpezkynfdrn
bcaeaae
aaaecbe
edcadcbcdd
abccdcddde
a
a
a
a
a
a
b
b
b
b
a
a
c
c
a
a
b
b
c
c
b
b
a
a
e
e
b
b
b
b
aa
aa
aa
aa
aa
aa
aa
aa
bb
bb
bb
bb
ba
ab
ca
ac
ab
ab
cb
bc
bb
bb
aa
aa
da
ad
ab
ab
cd
cd
aaa
aaa
aaa
aaa
aaa
aaa
aab
aab
aaa
aaa
baa
aab
bab
abb
baa
aab
ccc
ccc
ddd
ddd
ccd
ccd
bca
acb
cde
cde
ece
cee
bdd
bdd
aaaa
aaaa
aaaa
aaaa
aaaa
aaaa
abaa
aaab
abab
aabb
bbbb
bbbb
bbba
abbb
caba
aabc
ccbb
bbcc
abac
aabc
daba
aabd
cdbb
bbdc
bddd
bddd
dacb
abcd
abcc
abcc
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
baaab
aaabb
aabbb
aabbb
aabaa
aaaab
abcba
aabcb
bacbc
abbcc
bacba
aabcb
bdbda
adbdb
accbb
abbcc
dbccc
bcccd
decca
acced
dbbdd
bbddd
accec
accce
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaaaa
bbbbab
abbbbb
bbbbab
abbbbb
aaaaba
aaaaab
cbbbcc
bbbccc
aaacac
aaaacc
bacbbc
abbbcc
cacacc
aacccc
badbdc
abbcdd
ddadad
aadddd
ccdece
cccede
eecade
acdeee
eabdcb
abbcde
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaabbaa
aaaaabb
baaabab
aaaabbb
bbababa
aaabbbb
bcccacc
acccbcc
cbbcccc
bbccccc
abacaaa
aaaaacb
ccdbdac
acdbdcc
bbacaba
aaabcbb
abbaccc
aabbccc
bdcbcab
abcbcdb
dabcbce
abbccde
abaaabe
aaaabbe
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
ababbbba
aaabbbbb
aaaaaaba
aaaaaaab
babbbaab
aaabbbbb
bcaccaab
aaabcccb
bbccaabc
aabccbbc
cacaaaac
aaaaaccc
daacbddc
aabccddd
cdbdcdaa
aadcdbdc
bccbdacd
acdbccbd
abbeaade
aaadebbe
ccabecba
aabcebcc
ececaead
aadecece
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aabaaabbb
aaaaabbbb
abbbbbaab
aaabbbbbb
bbbaababb
aaabbbbbb
babcaaccb
aaabcccbb
ccbcabaac
aaabcbccc
caaaccccb
aaabccccc
abbcdbddb
abbbbdddc
dbcaacbbb
aabbbccbd
cadcbddac
aacddbcdc
ecebadadb
aabddbece
bdbeeccdd
bbccddeed
daaedecda
aaadceded
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
abaaaaabbb
aaaaaabbbb
bbaaaabaaa
aaaaaaabbb
bbabbaaaaa
aaaaaabbbb
cbaabcaacc
aaaacbbccc
aaaaccccab
aaaaabcccc
bccaccaacc
aaaccccbcc
dbdccdcacd
accdccdbdd
caaddaaccb
aaaabccddc
adbbabcbdc
aabbbbccdd
cdeabdbbad
aabbdbdedc
eeddcbeeec
bcceeeddee
bbcebddeba
abeddbecbb
def check_mayor(letra, lista):
    for i in lista:
        if (letra >= i):
            return False
    else:
        return True



if __name__ == '__main__':
    string = input()
    s = list(string)
    inicial = len(s)
    t = list()
    u = list()
    while (len(s) != 0):
        if (len(t) == 0):
            agregar = s[0]
            del s[0]
            t.append(agregar)
        elif (check_mayor(t[-1],s)):
            agregar = t[-1]
            del t[-1]
            u.append(agregar)
        else:
            agregar = s[0]
            del s[0]
            t.append(agregar)
    while (len(u) != len(string)):
        u.append(t[-1])
        del t[-1]
    string_f = ""
    for i in u:
        string_f += i
    print(string_f)
        
