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
al = [0]*26
bs = ord('a')
s = [ord(x)-bs for x in list(input())]
st = []
for x in s:
    al[x] += 1

cm = -1
for i in range(26):
    if al[i]:
        cm = i
        break

anso = []
for x in s:
    if x == cm:
        anso.append(x)
        al[cm] -= 1
        if not al[cm]:
            for i in range(cm,26):
                if al[i]:
                    cm = i
                    break
            while st and st[-1] <= cm:
                anso.append(st.pop())
    else:
        al[x] -= 1
        st.append(x)
ans = ''
for x in anso:
    ans += chr(bs+x)
for x in st[::-1]:
    ans += chr(bs+x)
print(ans)
