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.io.*;
import static java.lang.Math.*;
public class Main
{  
    static MyScanner scan;
    static PrintWriter pw;
    public static void main(String[] args) {
        new Thread(null,null,"_",1<<25)
        {
           public void run()
           {
               try
               {
                   solve();
               }
               catch(Exception e)
               {  
                   e.printStackTrace();
                   System.exit(1);
               }
           }
        }.start();
    }
    static void solve() throws IOException
    {
        scan = new MyScanner();
        pw = new PrintWriter(System.out,true);
        StringBuilder sb = new StringBuilder();
        char c[] = ne().toCharArray();
        int n = c.length;
        int next[] = new int[n+1];
        char min = c[n-1];
        next[n-1] = n-1;
        next[n] = n;
        for(int i=n-2;i>=0;--i)
        {
            if(c[i]<=min)
            {
                min = c[i];
                next[i] = i;
            }
            else next[i] = next[i+1];
        }
        Stack<Character> st = new Stack();
        int idx = 0;
        while(idx<n || !st.isEmpty())
        {
            if(st.isEmpty())
            {  
                int minidx = next[idx];
                while(idx<minidx)
                    st.add(c[idx++]);
                sb.append(c[idx++]);
            }
            else if(idx==n)
               sb.append(st.pop());
            else
            {
                if(c[next[idx]]<st.peek())
                {  
                    int minidx = next[idx];
                    while(idx<minidx)
                        st.add(c[idx++]);
                    sb.append(c[idx++]);
                }
                else sb.append(st.pop());
            }
        }
        psb(sb);
        pw.flush();
        pw.close();
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}