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 as inp

s = list(inp.readline()[:-1])
s.reverse()

ns = len(s)
currentns = ns
si = [(s[i], i) for i in range(ns)]
t = []
nt = 0
u = []
nu = 0

ordered = sorted(si, key = lambda x: (x[0], -x[1]))
j = 0

while(True):
    while (ordered[j][1] >= currentns):
        j += 1

    while (nt > 0 and ordered[j][0] >= t[-1]):
        u.append(t.pop())
        nu += 1
        nt -= 1
    
    nToT = (currentns-1) - ordered[j][1]
    for i in range(nToT):
        t.append(s.pop())
    u.append(s.pop())
    currentns = currentns - (nToT+1)
    nt += nToT
    nu += 1

    if(currentns == 0):
        while (nt > 0):
            u.append(t.pop()) 
            nt -= 1 # nu += 1
        print("".join(u))
        break