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
s = raw_input().strip()

def chrToInt(c):
	return ord(c) - ord('a')

def isSmallest(c, d):
	i = chrToInt(c)
	for idx in xrange(i-1, -1, -1):
		if d[idx] > 0:
			return False
	return True

queue = []
d = [0]*26

n = len(s)
res = ''
if n == 1:
	print s
else:

	for c in s:
		d[chrToInt(c)] += 1

	for c in s:

		queue.append(c)
		d[chrToInt(queue[-1])] -= 1
		# print 'adding ' + c
		while len(queue) > 0 and isSmallest(queue[-1], d):
			res += queue[-1]
			# print 'popping ' + queue[-1] + ' from queue and appending'
			

			queue.pop()
			# print d, queue

	while len(queue) > 0:
		res += queue[-1]
		queue.pop()
	print res