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
//package educational19;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * Created by ppetrov on 5/26/2017.
 */
public class C {

  public static void main(String[] args) throws IOException {

    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    String s = bufferedReader.readLine();

    final int length = s.length();
    char minimal = s.charAt(length -1);

    boolean [] isThereSmallerAfter = new boolean[length];
    char minimalAfter [] = new char[length];
    
    isThereSmallerAfter[length-1] = false;
    minimalAfter[length-1] = '/';
    
    for (int i=length-2;i>=0;i--) {
      if (minimal < s.charAt(i)) {
        isThereSmallerAfter[i] = true;
        minimalAfter[i] = '/';
      } else {
        minimalAfter[i] = minimal;
        minimal = s.charAt(i);
      }
    }

    Stack<Character> tString = new Stack<>();
    StringBuilder result = new StringBuilder();
    for (int i=0;i<length;i++) {
      if (isThereSmallerAfter[i]) {
        tString.push(s.charAt(i));
      } else {
        while (!tString.isEmpty() && tString.peek() <= s.charAt(i)) {
          result.append(tString.pop());
        }
        
        result.append(s.charAt(i));

        while (!tString.isEmpty() && tString.peek() <= minimalAfter[i]) {
          result.append(tString.pop());
        }
      }
    }
    
    while (!tString.isEmpty()) {
      result.append(tString.pop());
    }

    System.out.println(result.toString());
  }
  
}
