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 sys import stdin, stdout
from collections import deque
sze = 26

s = stdin.readline().strip()
second = []
third = []

position = [-1 for i in range(sze)]
for i in range(len(s)):
    position[ord(s[i]) - ord('a')] = i


i = 0
for k in range(sze):
    if position[k] == -1:
        continue
    
    while (second and ord(second[-1]) - ord('a') <= k):
        third.append(second.pop())    
    
    while i <= position[k]:
        if ord(s[i]) - ord('a') == k:
            third.append(s[i])
        else:
            second.append(s[i])
        
        i += 1

third.extend(second[::-1])
stdout.write(''.join(third))