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
from string import ascii_lowercase
s = input()
cursor = 0

dct = dict.fromkeys(ascii_lowercase,0)
for i in s:
    dct[i] += 1

fin = ''
curr = []
for j in dct.keys():
    while dct[j] != 0 and cursor != len(s):
        try:
            if ord(curr[-1]) <= ord(j):
                fin += curr[-1]
                curr.pop()
            else:
                if s[cursor] == j:
                    fin += s[cursor]
                else:
                    curr.append(s[cursor])
                dct[s[cursor]] -= 1
                cursor += 1
        except:
            if s[cursor] == j:
                fin += s[cursor]
            else:
                curr.append(s[cursor])
            dct[s[cursor]] -= 1
            cursor += 1
    if cursor == len(s):
        for k in range(len(curr)-1,-1,-1):
            fin += curr[k]
        break
print(fin)
