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 sys
import heapq

def solve(input_str):
    heap = []
    input_list = list(input_str)

    for idx, letter in enumerate(input_list):
        heapq.heappush(heap, (letter, idx))

    soln_str = ""
    stack = []
    cur_idx = 0

    while heap:
        char, idx = heapq.heappop(heap)
        if stack and char >= stack[-1]:
            while stack and char >= stack[-1]:
                soln_str += stack.pop()
        else:
            while cur_idx <= idx:
                if cur_idx == idx:
                    soln_str += input_list[cur_idx]
                else:
                    stack.append(input_list[cur_idx])
                cur_idx += 1
    soln_str += "".join(stack[::-1])
    return soln_str
                        
if __name__ == "__main__":
    str1 = sys.stdin.readline().strip()
    print solve(str1)
