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
def func(letra):
	for k in xrange(26):
		if alpha[k] < letra and freq[k]:
			
			return False
	return True

alpha = 'abcdefghijklmnopqrstuvwxyz'
freq = 26 * [0]

i = 1
s = raw_input()

for k in s:
	freq[ord(k) - 97] += 1



sti = [s[0]]


string_final = ''
freq[ord(sti[-1]) - 97] -= 1

while i < len(s):
	
	if len(sti) == 0:
		sti.append(s[i])
		i += 1
		freq[ord(sti[-1]) - 97] -= 1
		
	else:
		if func(sti[-1]):
			string_final += sti.pop()
	
		else:
			sti.append(s[i])
			i += 1
			freq[ord(sti[-1]) - 97] -= 1

while len(sti):
	string_final += sti.pop()
	
print string_final

			    	   	    			 		 		 		 		