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
def is_smallest(lst,pr,s):
    
    j = ord(s) - ord('a')
    
    for i in range(0,j):
        if lst[i]>0:
            return False
    return True
    

inp_str = list(input())
res = ''
alpha = [0]*26
qu = []

for i in range(0, len(inp_str)):
    j = ord(inp_str[i])-ord('a')
    alpha[j] += 1


for x in inp_str:
    
    qu.append(x)
    k = ord(x)-ord('a')
    alpha[k] -= 1
    while is_smallest(alpha,qu, x):
        res += qu.pop()
        if not qu:
            break
        x = qu[-1]

while qu:
    res += qu.pop()
    
print(res)