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()
n=[]
for i in range(len(s)):
    n.append("z")
n[-1] = s[-1]
a = s[-1]
for i in range(len(s)-2, -1, -1):
    if a>s[i]:
        a=s[i]
    n[i] = a
index= n.index(min(n))
q = []
u= ''
for i in range(len(s)):
    while q and q[-1] <= n[i]:
        u += q.pop()
    q.append(s[i])
print(u+ ''.join(map(str, (q[::-1]))))