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
q_string = str(input())
l = len(q_string)
queue_list = [[0,0] for i in range(l)]
for i in range(l):
    index = l-i-1
    if index==l-1:
        queue_list[index][0] = index
        queue_list[index][1] = q_string[index]
        continue
    else:
        if queue_list[index+1][1] < q_string[index]:
            queue_list[index][1] = queue_list[index+1][1]
            queue_list[index][0] = queue_list[index+1][0]
        else:
            queue_list[index][1] = q_string[index]
            queue_list[index][0] = index

s_stack = []
curr_index=0
output_string=[]
#print(queue_list)
while len(output_string)!=l:
    #print(curr_index)
    min_q = queue_list[curr_index][1]
    min_index_q = queue_list[curr_index][0]
    #minimum in the q
    len_stack = len(s_stack)
    min_s = 'zz' if len_stack == 0 else s_stack[len_stack-1]

    if min_q < min_s:
        for j in range(curr_index,min_index_q):
            s_stack.append(q_string[j])
        
        output_string.append(q_string[min_index_q])
        curr_index = min_index_q+1
    
    else:
        output_string.append(s_stack[len_stack-1])
        s_stack.pop()

    if curr_index>=l:
        #All things in queue have been exhausted
        
        while len(s_stack)!=0:
            
            output_string.append(s_stack.pop())
        break

print("".join(output_string))







    
        

    