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
s=input()
n=len(s)
cur=('z',n)
mi=[cur for _ in range(n)]
ns=mi[:]
for i in range(n-1,-1,-1):
    if (s[i],i)<cur:
        cur=(s[i],i)
    mi[i]=cur
    ns[i]=(s[i],i)
pos=0
cache=list()
res=''

while len(res)<n:
    c,i=mi[pos]
    res+=c
    cache+=ns[pos:i]
    pos=i
    if  cache:
        val, _ =cache[-1]
        mi[pos]=(val,pos)
        ns[pos]=(val,pos)
        if pos<n-1:
            mi[pos]=min(mi[pos],mi[pos+1])
        cache.pop()
    else:
        pos+=1
        
        
print( res   ) 
