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
# s = input().strip()

# s_list = list(s)

# t = []
# u = []
# i = 0

# while i < len(s):
#     if s_list[0] == min(s_list):
#         if t:
#             if (s_list[0] < t[-1]):
#                 u.append(s_list[0])
#             else:
#                 while t and s_list[0] >= t[-1]:
#                     u.append(t.pop())
#                 t.append(s_list[0])
#         else:
#             u.append(s_list[0])
#     else:
#         t.append(s_list[0])

#     del s_list[0]

#     # print(t, u)
#     i += 1

# if t:
#     u.extend(reversed(t))

# print(*u, sep="")

s = input()
a = [0]*26
for i in s:
    a[ord(i)-97] += 1
t, u = [], []
for i in s:
    t.append(i)
    a[ord(i)-97] -= 1
    while t and sum(a[:ord(t[-1])-97]) == 0:
        u.append(t.pop())
    # print(u)
print(''.join(u))
