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 findout(s):
    from collections import defaultdict
    dic=defaultdict(list)
    for i in range(len(s)):
        dic[s[i]]+=[i]
    possible=sorted([x for x in dic])
    stack=[]
    #ans=""
    index=-1
    checked=[0]*len(s)
    for x in possible:
        #print(stack)
        stop=dic[x][-1]
        if stop<index:
            continue
        
        if stack:
            while ord(stack[-1])<=ord(x):
                print(stack.pop(),end="")
                #ans+=stack.pop()
                if not stack:
                    break
        for i in range(index+1,stop+1):
            if s[i]!=x:
                stack+=[s[i]]
            else:
                if checked[i]==0:
                    checked[i]=1
                    #ans+=s[i]
                    print(s[i],end="")
        index=stop
    while stack:
        print(stack.pop(),end="")
        #ans+=stack.pop()
    #return ans
findout(input())