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
st = raw_input()
min_char = [0] * len(st)
min_char_index = -1
prev_min_char_index = -1

for i in range(len(st))[::-1]:
    min_char[i] = min_char_index
    if st[i] <= st[min_char_index]:
        min_char_index = i

left_string = []
min_string = []

while min_char_index != -1:
    if len(left_string) == 0  or (len(left_string) > 0 and len(left_string[-1]) > 0 and st[min_char_index] < left_string[-1][-1]):
        min_string.append(st[min_char_index])

        if prev_min_char_index == -1:
            if st[: min_char_index] != "":
                left_string.append(st[: min_char_index])
        else:
            if st[prev_min_char_index+1: min_char_index] != "":
                left_string.append(st[prev_min_char_index+1: min_char_index])

        prev_min_char_index = min_char_index
        min_char_index = min_char[min_char_index]
    elif len(left_string) > 0 and len(left_string[-1]) > 0:
        min_string.append(left_string[-1][-1])
        left_string[-1] = left_string[-1][:-1]
        if left_string[-1] == "":
            left_string.pop()

print "".join(min_string) + "".join(left_string)[::-1]