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 collections import OrderedDict
s=list(raw_input())
d=OrderedDict()
s1=sorted(s)
for i in s1:
    d[i]=d.get(i,0)+1
stack=[]
j=0
o=""
for i in d:
    #print i
    while(d[i]!=0 and j!=len(s)):
        if(stack!=[] and stack[-1]<=i):
            
            o=o+stack.pop()
            
        elif(s[j]==i):
            o+=s[j]
            d[i]-=1
            j+=1
        else:
            stack.append(s[j])
            d[s[j]]-=1
            j+=1
        
        
    if(j==len(s)):
        o+="".join(stack[::-1])
        break
        
print o    

    

    
    
