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
input_str = input()
s = []
t = []
u = []
for x in input_str:
    s.append(x)
s.reverse()
var = 97
while len(s) != 0 or len(t) != 0:
    track = len(s)
    for z in range(len(s)-1, -1, -1):
        if s[z] == chr(var):
            track = z
            for y in range(len(s)-1, z, -1):
                t.append(s[y])
                s.pop()
            u.append(s[z])
            s.pop()
    var += 1
    while True:
        if len(t) != 0 and ord(t[len(t)-1]) <= var:
            u.append(t[len(t)-1])
            t.pop()
        else:
            break
output_str = ""
for z in u:
    output_str += z
print(output_str)









