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.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
public class Minimal{//PRACTICE18
	public static void main(String args[]){
		FastScanner sc=new FastScanner(System.in);
        String s=sc.nextLine();
        int n=s.length();
        Stack<Character> s1=new Stack<>();
        TreeMap<Character,Integer> map = new TreeMap<>();
        for(int i=0;i<n;i++){
            char ch=s.charAt(i);
            if(map.containsKey(ch)){
                int k=map.get(ch);
                map.put(ch,k+1);
            }
            else
                map.put(ch,1);
        }
        String q="";
        int k=0;
        while(!map.isEmpty() || !s1.isEmpty()){
            if(map.isEmpty()){
                while(!s1.isEmpty())
                    //q=q+s1.pop();
                    System.out.print(s1.pop());
            }
            else if(s1.isEmpty() || s1.peek()>map.firstKey()){
                char ch=s.charAt(k);
                s1.push(ch);
                int x=map.get(ch);
                if(x==1)
                    map.remove(ch);
                else
                    map.put(ch,x-1);
                k++;
            }
            else{
                //q=q+s1.pop();
                System.out.print(s1.pop());
            }
        }
        System.out.println();
	}
	static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new
                    InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}