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
import sys
import heapq
def get_string(): return sys.stdin.readline().strip()


# Output for list
# sys.stdout.write(" ".join(map(str, final)) + "\n")

# Output for int or str
# sys.stdout.write(str(best) + "\n")



def solve(s):
  length = len(s)
  current = 97
  final = []
  start = 0
  end = length - 1
  extra = []

  while start <= end and current <= 122:
    ele = chr(current)
    temp = end
    flag = 0


    while extra:
      if extra[-1] <= ele:
        final.append(extra[-1])
        extra.pop()
      else:
        break
    
    # extra.reverse()

    while temp >= start:
      if s[temp] <= ele:
        flag = 1
        break
      else:
        temp -= 1
    
    if flag == 1:

      for i in range(start, temp+1):
        if s[i] <= ele:
          final.append(s[i])
        else:
          extra.append(s[i])
      

      start = temp + 1
      end = length - 1
    
    current += 1
  
  extra.reverse()
  final.extend(extra)
  sys.stdout.write("".join(map(str, final)) + "\n")
  return

  

s = get_string()
solve(s)