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
dic = {}
from string import lowercase

def check(x):
	hehe = 0
	for i in lowercase:
		if i == x:
			return hehe
		hehe += dic[i]

s = raw_input()
for i in lowercase:
	dic[i] = s.count(i)
ans = []
temp = []
for i in s:
	dic[i] -= 1
	temp.append(i)
	while len(temp) and check(temp[-1]) == 0:
		ans.append(temp.pop())
print ''.join(ans)
