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

ptr = ord('a')


def s_has_smaller(s_cnt_local, c):
    global ptr
    for i in range(ptr, ord(c)):
        ptr = i
        if s_cnt_local[i] > 0:
            return True
    return False


s = list(input())
s.reverse()


t = []
u = []

s_cnt = [0] * (ord('z')+1)
for x in s:
    s_cnt[ord(x)] += 1


while s or t:
    # print('+'*10)
    # print(s)
    # print(t)
    # print(u)
    # print(s_cnt)
    # print(t_cnt)
    if not s:
        while t:
            u.append(t.pop())
    elif not t:
        x = s.pop()
        s_cnt[ord(x)] -= 1
        t.append(x)
    else:
        if s_has_smaller(s_cnt, t[-1]):
            x = s.pop()
            s_cnt[ord(x)] -= 1
            t.append(x)
        else:
            x = t.pop()
            u.append(x)

print("".join(u))
