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
from collections import deque
s = deque(input())

t = []
u = []

ch = 'a'
while len(s) != 0:
	#print(ch)
	#print('s = {}\nt = {}\nu = {}\n\n'.format(s,t,u))
	if ch in s:
		while len(t) > 0 and t[-1] <= ch:
			u.append(t.pop())
		n = s.count(ch)
		for _ in range(n):
			while s[0] != ch:
				t.append(s.popleft())
			u.append(s.popleft())
			
			
	ch = chr(ord(ch) + 1)
	
while len(t) != 0:
	u.append(t.pop())
	
print(''.join(x for x in u))
