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
#!/usr/bin/pypy3

# s[0] -> t[-1] or t[-1]->u[-1]
# "cab" ->("cab","","")->("ab","c","")->("b","ca","")->("b","c","a")
# 1) stack s->t until min(s).
# 2) passthrough min(s)->u
# min(s,t[-1]) -> u. Repeat.
# need to know the smallest item in s (quickly)
# think it's: split into two subsequences, merge s1(reverse)+s2. minimum.
# "cab" -> s1="cb",s2="a" -> bc
# "dcab" -> "b","dca"
from sys import stdin,stderr

def readInts(): return map(int,stdin.readline().strip().split())
def print_err(*args,**kwargs): print(*args,file=stderr,**kwargs)
    
def solve(s):
    s = list(s)
    sn = len(s)
    pq = sorted(zip(list(s),range(sn)))
    ix_left = 0
    u,v = [],[]
    for c,ix in pq:
        if ix < ix_left: continue
        while u and c >= u[-1]: v.append(u.pop())
        for cix in range(ix_left,ix+1): u.append(s[cix])
        ix_left = ix+1
    while u: v.append(u.pop())
    return v    

def run():
    s = input().strip()
    print("".join(solve(s)))
        
run()
