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
def main():
    s = list(input())

    suffix = []
    for x in reversed(s):
        if suffix:
            suffix.append(min(suffix[-1], x))
        else:
            suffix.append(x)

    suffix = suffix[::-1]

    u = []
    t = []
    i = 0

    while True:
        m = suffix[i]

        while t and t[-1] <= m:
            u.append(t[-1])
            t.pop()

        while s[i] != m:
            t.append(s[i])
            i += 1

        u.append(s[i])

        i += 1
        if i == len(s):
            break

    u += t[::-1]

    print(''.join(u))


if __name__ == '__main__':
    main()
