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 sys import stdin,stdout
def min(s):
    fr=[0]*27
    l=[]
    for i in s:
        x=ord(i)-96
        fr[x]+=1
        l.append(x)
    stk=[]
    sf=[0]*27
    ans=[]
    i=0
    n=len(s)
    while i<n:
        if len(stk)==0:
            for j in range(len(fr)):
                if fr[j]>0:
                    break
            k=i
            while l[k]!=j:
                stk.append(l[k])
                fr[l[k]]-=1
                sf[l[k]]+=1
                k+=1
                i+=1
            ans.append(l[k])
            fr[l[k]]-=1
            i+=1
        else:
            tp=stk[-1]
            flg=0
            for j in range(tp):
                if fr[j]>0:
                    flg=1
                    break
            if flg==1:
                k=i
                while l[k]!=j:
                    stk.append(l[k])
                    sf[l[k]]+=1
                    fr[l[k]]-=1
                    k+=1
                    i+=1
                i+=1
                ans.append(j)
                fr[j]-=1
            else:
                x=stk.pop()
                ans.append(x)
                sf[x]-=1
    while len(stk)!=0:
        ans.append(stk.pop())
    for i in ans:
        stdout.write(chr(i+96))
s=stdin.readline().strip()
min(s)
