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 collections import deque

s = deque(input())
t = deque()
u = ''
alphabet = list('abcdefghijklmnopqrstuvxwyz')
dic = { k: i for i, k in enumerate(alphabet) }
c = [0 for l in alphabet]
for l in s:
    c[dic[l]] += 1

j = 0
while len(s) > 0:
    curr = s[0]
    desired = alphabet[j]
    flag = False
    while len(t) > 0 and t[-1] <= desired:
        flag = True
        u += t.pop()

    if not c[j] and j < len(c) - 1:
        j += 1
        continue

    while len(s) > 0 and s[0] == desired:
        flag = True
        c[j] -= 1
        u += s.popleft()

    if not flag:
        c[dic[curr]] -= 1
        t.append(s.popleft())

while len(t) > 0:
    u += t.pop()

print(u)

  				      	   	  			   	   		