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 atexit, io, sys, collections, math, heapq, fractions
buffer = io.BytesIO() 
sys.stdout = buffer
@atexit.register 
def write(): sys.__stdout__.write(buffer.getvalue())
#####################################

def f(s):
	s = [ord(e) -ord('a') for e in list(s)]
	mins = s[::]
	for i in range(len(s)-2,-1,-1): mins[i] = min(mins[i+1], mins[i])
	
	u = []
	t = collections.deque([])
	i = 0
	while(i < len(s)):
		
		# whats the next one that we can get 

		if len(t) == 0 or mins[i] < t[-1]:
			while(i<len(s) and s[i] != mins[i]):
				t.append(s[i])
				i += 1
			if i < len(s) and s[i] == mins[i]:
				u.append(s[i])
				i +=1
		else:
			u.append(t.pop())

	while(t): u.append(t.pop()) 
	return ''.join(map(lambda x:chr(x+ord('a')), u))

print f(raw_input())