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.io.*;
import java.lang.*;
import java.util.*;

public class C797 {
    public static void main(String[] args) throws IOException{
        StringBuffer ans = new StringBuffer();
        StringTokenizer st;
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(f.readLine());
        String s = st.nextToken();
        int n = s.length();
        point[] arr = new point[n];
        for(int i = 0; i < n; i++){
            arr[i] = new point(s.charAt(i), i);
        }
        f.close();
        //System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);
        //System.out.println(Arrays.toString(arr));
        int prev = -1;
        Stack<Character> stack = new Stack();
        for(int i = 0; i < n; i++){
            //System.out.println(stack);
            if(arr[i].y > prev && (stack.empty() || arr[i].x < stack.peek())){
                ans.append(s.charAt(arr[i].y));
                for(int x = prev+1; x < arr[i].y; x++){
                    stack.push(s.charAt(x));
                }
            }else if(arr[i].y > prev){
                //System.out.println(stack.peek() <= arr[i].x);
                while(!stack.empty() && (int)stack.peek() <= arr[i].x){
                    ans.append(stack.pop());
                }
                ans.append(s.charAt(arr[i].y));
                for(int x = prev+1; x < arr[i].y; x++){
                    stack.push(s.charAt(x));
                }
            }
            prev = Math.max(arr[i].y, prev);
        }
        while(!stack.empty()){
            ans.append(stack.pop());
        }
        System.out.println(ans);
    }
    public static class point implements Comparable<point>{
        int x;
        int y;
        public point(int x,int y){
            this.x = x;
            this.y = y;
        }
        public String toString(){
            return(x + " " + y);
        }
        public boolean equals(Object x){
            point y = ((point)(x));
            if (this.x == y.x && this.y == y.y){
                return true;
            }
            return false;
        }
        public int hashCode(){
            return Objects.hash(x,y);
        }
        public int compareTo(point other){
            if(this.x > other.x || (this.x == other.x && this.y > other.y)){
                return 1;
            }else if(this.x == other.x && this.y == other.y)
                return 0;
            return -1;
        }
    }
}