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 E19C
{
    static PrintWriter out=new PrintWriter((System.out));
    public static void main(String args[])throws IOException
    {
        Reader sc=new Reader();
        String s=sc.next();
        int n=s.length();
        int ar[]=new int[26];
        for(int x=0;x<n;x++)
        {
            ar[s.charAt(x)-97]++;
        }
        Stack<Character> stack=new Stack<Character>();
        StringBuilder ans=new StringBuilder("");
        for(int x=0;x<n;x++)
        {
            char ch=s.charAt(x);
            stack.push(ch);
            int d=ch-97;
            ar[d]--;
            boolean found=false;
            while(!found&&!stack.isEmpty())
            {
                char c=stack.peek();
                for(int y=0;y<c-97;y++)
                {
                    if(ar[y]>0)
                    {
                        found=true;
                        break;
                    }
                }
                if(!found)
                {
                    ans.append(stack.pop());
                }
            }
        }
        while(!stack.isEmpty())
        {
            ans.append(stack.pop());
        }
        out.println(ans);
        out.close();
    }
    static class Reader 
    { 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next()
        {
            while(!st.hasMoreTokens())
            {
                try
                {
                    st=new StringTokenizer(br.readLine());
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        public long nextLong()
        {
            return Long.parseLong(next());
        }

        public double nextDouble()
        {
            return Double.parseDouble(next());
        }

        public String nextLine()
        {
            try
            {
                return br.readLine();
            }
            catch(Exception e)
            {
                e.printStackTrace();
            }
            return null;
        }

        public boolean hasNext()
        {
            String next=null;
            try
            {
                next=br.readLine();
            }
            catch(Exception e)
            {
            }
            if(next==null)
            {
                return false;
            }
            st=new StringTokenizer(next);
            return true;
        }
    } 
}