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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.Deque;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author avsingh
 */
public class Code_force {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner scan=new Scanner(System.in);
        String s=scan.next();
        char a[]=new char[100010];
        char m='z'+2;
        Stack<Character> stak=new Stack<Character>();
        for(int i=s.length()-1;i>=0;i--){
            if(m>s.charAt(i))
                m=s.charAt(i); 
            a[i]=m;
            
            
        }
        for(int i=0;i<s.length();i++){
         
            while(!stak.empty() && stak.peek()<=a[i]){
                System.out.print(stak.peek());
                stak.pop();
            } 
            stak.push(s.charAt(i));
        }
        while(!stak.empty()){
            System.out.print(stak.peek());
            stak.pop();
        }
        System.out.println();
        
    }
    
}
