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
import heapq
s=raw_input()
heap=[]
s=list(s)
for idx, letter in enumerate(s):
    heapq.heappush(heap, (letter, idx))
ans=""
stack=[]
cur_idx=0
while heap:
    char, idx=heapq.heappop(heap)
    if stack and char>=stack[-1]:
        while stack and char>=stack[-1]:
            ans+=stack.pop()
    else:
        while cur_idx<=idx:
            if cur_idx<>idx:
                stack.append(s[cur_idx])
            else:
                ans+=s[cur_idx]
            cur_idx+=1 
print  ans