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 codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;



/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
         static class Input {
        private StringTokenizer tokenizer = null;
        private BufferedReader reader;
 
        public Input(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }
 
        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
        public int[] nextIntArray(int n, int add) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = nextInt() + add;
            }
            return result;
        }
 
        public long[] nextLongArray(int n, long add) {
            long[] result = new long[n];
            for (int i = 0; i < n; i++) {
                result[i] = nextLong() + add;
            }
            return result;
        }
 
        public int[] nextIntArray(int n) {
            return nextIntArray(n, 0);
        }
 
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		Input s=new Input(System.in);
		int t=1;
		while(t-->0)
		{
		    String st=s.next();
		    int prev=0;
		    int n=st.length();
		    int a[]=new int[n];
		    a[n-1]=n-1;
		    for(int i=n-2;i>=0;i--)
		    {
		        if(st.charAt(i)<=st.charAt(a[i+1]))
		        a[i]=i;
		        else
		        a[i]=a[i+1];
		        //System.out.print(a[i]+" ");
		    }
		    //System.out.println();
		    
		    
		    
		    Stack<Character> sta=new Stack<>();
		    while(prev<=n-1)
		    {
		        int in=a[prev];
		        //System.out.println("in"+" "+prev+" "+st.charAt(in));
		        
		        
		        while(!sta.isEmpty() && sta.peek()<=st.charAt(in))
		        System.out.print(sta.pop());
		        
		        
		        for(int i=prev;i<in;i++)
		        {
		            sta.push(st.charAt(i));
		        }
		        
		        sta.push(st.charAt(in));
		        prev=in+1;
		        
		    }
		    while(!sta.isEmpty())
		    System.out.print(sta.pop());
		    System.out.println();
		}
	}
}
