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
# sys.stdin = open('D:\\codes\\ccdsap prepare\\in.txt', 'r')
# sys.stdout = open('D:\\codes\\ccdsap prepare\\out.txt', 'w')

def compare(a, vis):
    for i in range(0, ord(a) - ord('a')):
        if vis[i] > 0:
            return False
    return True

n = input()
vis = [0] * 26
for letter in n:
    vis[ord(letter) - ord('a')] = vis[ord(letter) - ord('a')] + 1
st = []
# print(vis)
s = []
for i in range(0, len(n)):
    st.append(n[i])
    vis[ord(n[i]) - ord('a')] = vis[ord(n[i]) - ord('a')] - 1
    while (len(st) > 0 and compare(st[len(st) - 1], vis)):
        s.append(st[len(st) - 1])
        st.pop()
    # print("s st", s, st)
while len(st) != 0:
    s.append(st[len(st) - 1])
    st.pop()
for letter in s:
    print(letter, end = '')
# print("Here ", s)
    # print(n)