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 = input()
iterate = 0
e = [(True) for i in range(len(s))]
ans = ['' for i in range(len(s))]
idx = 0

lastOccur = [-1 for i in range(26)]

for i in range (len(s)):
	lastOccur[ord(s[i])-ord('a')] = i

i = 0
while(i < 26 and iterate < len(s)):
	j = iterate-1
	while(j >= 0 and ord(s[j]) - ord('a') <= i):
		if(e[j]):
			ans[idx] = s[j]
			e[j] = False
			idx += 1
		j -= 1

	j = iterate
	while(j < lastOccur[i]+1):
		if(e[j] and ord(s[j])-ord('a') == i):
			ans[idx] = s[j]
			e[j] = False
			idx += 1
		j += 1
	iterate = j
	i += 1

if(iterate >= len(s)):
	for j in range(len(s)-1, -1, -1):
		if(e[j]):
			ans[idx] = s[j]
			idx += 1


#print(ans)
str1 = ''.join(ans)
print(str1)