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
//Complete this code or write your own from scratch
import java.util.*;
import java.io.*;
import java.math.*;

public class Solution{
    
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 25;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[1280000]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
    }
    
    static StringBuffer s;
    static Stack<Character> stack;
    static int[] arr;
    public static void main(String[] argh) throws Exception{
        // Reader br = new Reader();
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        s= new StringBuffer(br.readLine().trim());
        stack= new Stack<>();
        int len= s.length();
        arr= new int[len];
        int currMin= 30;
        for(int i=len-1; i>=0; i--){
            char ch = s.charAt(i);
            int pos= ch - 97;
            if(pos <= currMin){
                currMin= pos;
                arr[i]= -1;
            }
            else{
                arr[i] = currMin;
            }
        }
        StringBuffer u= new StringBuffer();
        for(int i=0; i<len; i++){
            if(arr[i] == -1){
                while(!stack.empty()){
                    int ch = stack.peek() - 97;
                    if(ch <= (s.charAt(i) - 97)){
                        u.append(stack.pop());
                    }
                    else{
                        break;
                    }
                }
                u.append(s.charAt(i));
            }
            else{
                while(!stack.empty()){
                    int ch = stack.peek() - 97;
                    if(ch <= arr[i]){
                        u.append(stack.pop());
                    }
                    else{
                        break;
                    }
                }
                stack.push(s.charAt(i));
            }
        }
        while(!stack.empty()){
            u.append(stack.pop());
        }
        System.out.println(u);
    }
}