Petya 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
#https://codeforces.com/contest/797/problem/C

#s is queue
#t is a stack
'''
def solve(s):
    suffix_min = []
    t = []
    u = []

    m = 'z'
    for c in reversed(s):
        m = min(m,c)
        suffix_min.append(m)

    for c,m in zip(s,reversed(suffix_min)):
        if c!=m:
            t.append(c)
        else:
            u.append(c)

    return "".join(u)+"".join(reversed(t))
'''

def get_min_char(freq):
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if freq[c]!=0:
            return c

def solve(s):
    suffix_min = []
    t = []
    u = []

    letters = 'abcdefghijklmnopqrstuvwxyz'
    freq = {c:s.count(c) for c in letters}

    for c in s:
        m = get_min_char(freq)

        while len(t)>0:
            top = t.pop()
            if top <= m:
                u.append(top)
            else:
                t.append(top)
                break

        if c>m:
            t.append(c)
        else:
            u.append(c)

        freq[c]-=1

    return "".join(u)+"".join(reversed(t))  

def main():
    print(solve(input()))

if __name__=="__main__":
    main()