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 random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter

input = sys.stdin.readline

# Function to call the actual solution
def solution(s):
	# s = s[::-1]
	a = []
	b = []
	indi = 0
	se = Counter(list(s))
	se1 = {}
	for i in list(s):
		if i == min(se.keys()):
			b.append(i)
		else:
			a.append(i)
			se1[i] = se1.get(i, 0) + 1
		se[i] -= 1
		if se[i] == 0:
			del se[i]
		while a and len(se) and a[-1] <= min(se.keys()):
			b.append(a.pop())
	while a:
		b.append(a.pop())
	return ''.join(b)


# Function to take input
def input_test():
	s = input().strip()
	out = solution(s)
	print(out)

# Function to test my code
def test():
	pass


input_test()
# test()