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 java.util.Scanner;
import java.util.Stack;

public class Main{
  static String s;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    s = sc.next();

    int[] counts = new int[26];
    for(int i = 0; i < s.length(); i++){
      ++counts[s.charAt(i) - 'a'];
    }

    char min = 'z';
    for(int i = 0; i < 26; i++){
      if(counts[i] >= 1){
        min = (char)(i + 'a');
        break;
      }
    }

    StringBuilder u = new StringBuilder();
    Stack< Character > stack = new Stack< >();
    int i = 0;
    while(i < s.length()){
      stack.push(s.charAt(i));
      --counts[s.charAt(i) - 'a'];
      ++i;
      for(int j = 0; j < 26; j++){
        if(counts[j] >= 1){
          min = (char)(j + 'a');
          break;
        }
      }
      while(!stack.isEmpty() && stack.peek() <= min){
        u.append(stack.pop());
      }
    }

    while(!stack.isEmpty()){
      u.append(stack.pop());
    }

    System.out.println(u);
  }
}