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
string = raw_input()

aux = ""
ans = ""
letras = "abcdefghijklmnopqrstuvwxyz"

alfa = {a: 0 for a in letras}
for b in string:
    alfa[b] += 1

i, a = 0, 0
tam = len(string)
j = -1

while i < tam:
    if a > 25:  break

    while alfa[letras[a]] == 0: a += 1

    if j > -1 and aux[-1] <= letras[a]:
        ans += aux[-1]
        aux = aux[0:-1]
        j -= 1
    elif string[i] == letras[a]:
        ans += string[i]
        alfa[letras[a]] -= 1
        i += 1
    else:
        alfa[string[i]] -= 1
        aux += string[i]
        j += 1
        i += 1

# -----------------------

j = len(aux) - 1
while j > -1:
    ans += aux[j]
    j -= 1

print ans

# vasyadidntwin
 	 		  	 	    	 		 			  			   	