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
import sys
#import random
from bisect import bisect_right as rb
from collections import deque
#sys.setrecursionlimit(10**8)
from queue import PriorityQueue
from math import *
input_ = lambda: sys.stdin.readline().strip("\r\n")
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab,bc,cd : ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x : print(x)
prinT = lambda x : print(x)
f = lambda : sys.stdout.flush()
inv =lambda x:pow(x,mod-2,mod)
mod = 10**9 + 7

s = list(ip())

suf = ['z' for i in range (len(s)+2)]

suf[len(s)-1] = s[len(s)-1]

for i in range (len(s)-1,0,-1) :
    suf[i-1] = min(s[i-1],suf[i])

ans = []

x = suf[0]
b = []
i = 0

while (i<len(s)) or (len(b) > 0) :
    #print(i,b)
    if (len(b) > 0) and b[len(b)-1] <= suf[i] :
        ans.append(b[len(b)-1])
        b.pop()
    else :
        b.append(s[i])
        i += 1

print(''.join(ans))
