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.util.*;
    public  class Solution{
        public static void main(String args[]){
            Scanner in=new Scanner(System.in);
            String str=in.nextLine();
            int n=str.length();
            Stack<Character> s=new Stack<>();
            char[] ch=str.toCharArray();
            char[] freq=new char[n];
            freq[n-1]=ch[n-1];
            for(int i=n-2;i>=0;i--){
                if(freq[i+1]>ch[i])freq[i]=ch[i];
                else freq[i]=freq[i+1];
            }
            Arrays.sort(ch);
            int ptr=0;
            StringBuilder u=new StringBuilder();
            //int i;
            for(int i=0;i<n && ptr<n;i++){
                if(str.charAt(i)==ch[ptr])u.append(ch[ptr++]);
                else if(!s.isEmpty() && s.peek()<=freq[i]){u.append(s.pop());i--;}
                else s.push(str.charAt(i));
            }
            while(!s.isEmpty())u.append(s.pop());
            System.out.println(u.toString());
            
        }
    }