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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


import java.util.StringTokenizer;


 public class Test
 {
    
    static PrintWriter pw = new PrintWriter(System.out);
    static char findMin(int[] ar)
    {
       for(int i = 0 ; i<26 ; i++)
           if(ar[i] > 0)
               return (char)((int)'a' + i);
       
       return '!';
    }
    public static void main(String[] args)throws Exception
    {
        Reader.init(System.in);
        String s = Reader.next();
        Stack<Character> t = new Stack();
        StringBuilder u = new StringBuilder();
        int[] ar = new int[26];
        int sL = s.length();
        char max = (char)((int)'a' - 1);
        for(int i = 0 ; i<sL ; i++)
        {
            char c = s.charAt(i);
            ar[c - 'a']++;           
        }
        
        for(int i = 0 ; i<sL ; i++)
        {
            char ch = s.charAt(i);
            t.push(ch);
            ar[ch - 'a']--;
            max = ch > max ? ch : max;
            char min = findMin(ar);
            while(!t.isEmpty())
            {
                char temp = t.peek();
                if(temp <= min)
                    u.append(t.pop());
                else
                    break;
            }
       
        }
        
        while(!t.isEmpty())
            u.append(t.pop());
       
        pw.print(u);
        pw.close();
        
    }
}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    public static int pars(String x) {
        int num = 0;
        int i = 0;
        if (x.charAt(0) == '-') {
            i = 1;
        }
        for (; i < x.length(); i++) {
            num = num * 10 + (x.charAt(i) - '0');
        }

        if (x.charAt(0) == '-') {
            return -num;
        }

        return num;
    }

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static void init(FileReader input) {
        reader = new BufferedReader(input);
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return pars(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}