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
#sys.stdin = open('in', 'r')
#n = int(input())
#a = [int(x) for x in input().split()]
#n,m = map(int, input().split())

s = input()
n = len(s)
mins=[ord('z')+1]*n

mins[-1] = s[-1]
for i in range(1, n):
    mins[-i-1] = min(mins[-i], s[-i-1])

a = []
r = ''
i = 0
j = 0
while i < n:
    while len(a) > 0 and a[-1] <= mins[i]:
        r += a.pop()
    mn = mins[i]
    while s[i] > mn:
        a.append(s[i])
        i += 1
    a.append(s[i])
    i += 1

while len(a) > 0:
    r += a.pop()
    
print(r)
