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 sys
from collections import defaultdict

s = list(sys.stdin.readline().strip())


'''
On every step you should maintain minimal alphabetic letter in current string s (this can be done by keeping array of 26 cells with number of times each letter appear in string nd updating it on every step). Let's call string t a stack and use its terms.

Now you extract letters from s one by one. Put the letter to the top of the stack. Pop letters from the top of stack and push them to answer while they are less or equal than any letter left in string s. After string s becomes empty push all the letters from stack to answer.

The answer will be lexicographically minimal. It is obvious if we consider the case when current top of stack is strictly greater than any character from the remaining string s, or there is a character in s that is strictly less than current top. If current top is equal to some character then appending answer with the letter from top won't make answer worse.

Overall complexity: O(n * |AL|), where |AL| is the length of the alpabet, 26 in our case.
'''

def min_char(char2count):
	alphabet = 'abcdefghijklmnopkrstuvwxyz'
	for char in alphabet:
		if char2count[char] > 0:
			return char

char2count = defaultdict(int)
for char in s:
	char2count[char] += 1

t, u = [], []

minc = min_char(char2count)

while len(s) > 0:
	if len(t) == 0:
		char = s.pop(0)

		t.append(char)
		char2count[char] -= 1
		if char2count[char] == 0:
			minc = min_char(char2count)

	elif t[-1] <= minc:
		u.append(t.pop())
	else:
		char = s.pop(0)

		t.append(char)
		char2count[char] -= 1
		if char2count[char] == 0:
			minc = min_char(char2count)
		

while len(t) > 0:
	u.append(t.pop())

print(''.join(u))
