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

s = input()
s = [x for x in s]

t, u = [], []

ds = defaultdict(int)

for c in s:
    ds[c] += 1

curr_letter_index = ord('a')
curr_poz_in_s = 0

while curr_letter_index <= ord('z'):
    curr_letter = chr(curr_letter_index)

    if len(t) > 0 and ord(t[-1]) <= ord(curr_letter):
        letter = t.pop()
        u.append(letter)
    else:
        if ds[curr_letter] > 0:
            letter = s[curr_poz_in_s]
            curr_poz_in_s += 1
            t.append(letter)
            ds[letter] -= 1
        else:
            curr_letter_index += 1

t.reverse()
print("".join(u + t))
