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.*;
import java.math.*;
import java.io.*;
import java.text.*;

public class A{

//public static PrintWriter pw; 	
public static PrintWriter pw=new PrintWriter(System.out);
public static void solve() throws IOException{
//	pw=new PrintWriter(new FileWriter("C:\\Users\\shree\\Downloads\\small_output_in"));
	FastReader sc=new FastReader();
	char s[]=sc.next().toCharArray();
	int a[]=new int[26];
	for(int i=0;i<s.length;i++)a[s[i]-'a']++;
	Stack<Character>stk=new Stack<>();
	StringBuilder ans=new StringBuilder("");
	
	for(int i=0;i<s.length;i++) {
	    a[s[i]-'a']--;
	    stk.push(s[i]);
	    while(!stk.isEmpty() && is(a,stk.peek())) {
	    	ans.append(stk.pop());
	    }
	}
	while(!stk.isEmpty()) ans.append(stk.pop());
	pw.println(ans);
	 pw.close(); 
	
	
}
static boolean is(int a[],char ch) {
	for(int j=0;j<ch-'a';j++)if(a[j]>0)return false;
	return true;
}

public static void main(String[] args)  {
    new Thread(null ,new Runnable(){
      public void run(){
          try{
          
              solve();
          } catch(Exception e){
              e.printStackTrace();
          }
      }
  },"1",1<<26).start();
 
}

static long M=(long)Math.pow(10,9)+7;
 
	static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() throws FileNotFoundException{
            //br=new BufferedReader(new FileReader("C:\\Users\\shree\\Downloads\\B-small-practice.in"));	
        	 br = new BufferedReader(new InputStreamReader(System.in));
        		
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
       
        int I(){   return Integer.parseInt(next()); }
        long L(){  return Long.parseLong(next()); }
        double D() {  return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
     }
}