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
from sys import stdin

lines, line_index = stdin.readlines(), -1


def get_line():
  global lines, line_index

  line_index += 1
  return lines[line_index]


def next_min_char(info):
  for k, v in enumerate(info):
    if v != 0:
      return k

  return -1

def main():
  data = get_line().strip()

  stack = []
  output = []
  a = ord('a')
  z = a + 26
  n = len(data)

  best = [-1] * (n + 1)
  best[n] = z

  for i in range(n - 1, -1, -1):
    best[i] = min(best[i + 1], ord(data[i]))

  cur = 0

  while stack or cur < n:
    if stack and ord(stack[-1]) <= best[cur]:
      output.append(stack.pop())
    else:
      stack.append(data[cur])
      cur += 1

  print(''.join(output))

main()