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.*;
/**
 * https://codeforces.com/contest/797/problem/C   
 */
public class Main{
 
    public static boolean isSmallExist(int[] characterHash, char elem) {
 
        int end_loc = elem; 
        //System.out.println("end loc is " + end_loc + " elem " + elem);
 
        //System.out.println(Arrays.toString(characterHash));
 
        for (int i = end_loc - 1; i >= 0; i--) {
            if (characterHash[i] > 0){
                //System.out.println  ("true");
                return true;
            }
        }
 
        //System.out.println("false");
 
        return false;
 
    }
 
    public static String findMinimalString(String s) {
 
        Stack<Character> t = new Stack<>();
 
        StringBuilder sb = new StringBuilder();
 
 
        int[] characterHash = new int[128];
 
        for (char ch : s.toCharArray()) {
            characterHash[ch]++;
        }
 
        int index = 0;
 
        while(index < s.length()){
 
            //System.out.println(Arrays.toString(characterHash));
 
            if (t.isEmpty()) {
                characterHash[s.charAt(index)]--;
                t.push(s.charAt(index++));
            } else {
 
                char curChar = t.peek(); 
                char nextChar = s.charAt(index);
 
                if (nextChar < curChar)  {
                    characterHash[s.charAt(index)]--;
                    t.push(s.charAt(index++));
                } else {
                     
                    if(!isSmallExist(characterHash, t.peek())) {
                        //System.out.println("ppop is " + t.peek());
                        sb.append(t.pop());
                    } else if (isSmallExist(characterHash, s.charAt(index))) {
                        //System.out.println("push" + s.charAt(index));
                        characterHash[s.charAt(index)]--;
                        t.push(s.charAt(index++));           
                    } else {
                        //System.out.println("pop is " + t.peek());
                        sb.append(t.pop());
                    }
 
                }
            }
 
        }
 
        while(!t.isEmpty()) {
            sb.append(t.pop()); 
        }
        
        //System.out.println(sb.toString());
        return sb.toString();
 
    }
 
    public static void main(String[] args) throws IOException{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        PrintWriter wr = new PrintWriter(System.out);
 
        String s = br.readLine();
 
        String minimalString = findMinimalString(s);
 
        wr.println(minimalString);
        wr.close();
        br.close();
        
        //assert findMinimalString("cab").compareTo("abc") == 0;
        //assert findMinimalString("acdb").compareTo("abdc") == 0;
        //assert findMinimalString("bababaaababaabbbbbabbbbbbaaabbabaaaaabbbbbaaaabbbbabaabaabababbbabbabbabaaababbabbababaaaaabaaaabbba").compareTo("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb") == 0;
        //assert findMinimalString("dijee").compareTo("deeji") == 0;        
    }
}