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
a = input()
b = list(a)
c = b[:]
c.sort()
t = []
answer = []
for i in range(len(c)):
    while(len(t) != 0 and c[i] >= t[len(t)-1]):
        #print("lil") 
        answer.append(t[len(t)-1])
        t.pop(len(t) -1)
    if(c[i] in b):
        if(b[0] == c[i]):
            answer.append(b[0])
            b.pop(0)
        else:
            while(b[0] != c[i]):
                t.append(b[0])
                b.pop(0)
            answer.append(b[0])
            b.pop(0)
if(len(t) != 0):
    for i in range(1,len(t)+1):
        answer.append(t[len(t)-i])

print("".join(answer))