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.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc=new Scanner(System.in);
        Stack<Character> st=new Stack<>();
        String a=sc.next();
        
        int freq[]=new int[26];
        
        for(int i=0;i<a.length();i++)
        {
            freq[a.charAt(i)-'a']++;
        }
        StringBuilder ans=new StringBuilder();
        for(int i=0;i<a.length();i++)
        {
            st.push(a.charAt(i));
            char top=st.peek();
            freq[top-'a']--;
            
            while(!st.isEmpty() && isCurMin(st.peek(),freq))
            {
                ans.append(Character.toString(st.pop()));
            }
            
        }
        System.out.println(ans.toString());
    }
    static boolean isCurMin(char top,int freq[])
    {
        for(int i=0;i<top-'a';i++)
        {
            if(freq[i]>0)
            return false;
        }
        return true;
    }
}