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.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class SSolution {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        SSolution s = new SSolution();
        s.solve(in);
    }

    private void solve(BufferedReader in) throws IOException {
        String s = in.readLine();
        Deque<Character> d = new LinkedList<Character>();

        TreeMap<Character, Integer> tm = new TreeMap<Character, Integer>();
        for(Character c: s.toCharArray()){
            if(tm.containsKey(c)){
                tm.put(c, tm.get(c) + 1);
            }
            else{
                tm.put(c, 1);
            }
        }

        TreeMap<Character, Integer> tm_copy = (TreeMap<Character, Integer>)tm.clone();

        ArrayList<Character> res = new ArrayList<Character>();

        Iterator<Character> iterator = tm.navigableKeySet().iterator();
        Character needed = iterator.next();
        for (int i = 0; i < s.length(); ++i) {
            Character curr = s.charAt(i);
            tm.put(curr, tm.get(curr) - 1);

            if (curr.equals(needed)) {
                res.add(needed);

                if (tm.get(needed) == 0) {
                    while (iterator.hasNext()) {
                        needed = iterator.next();

                        while (d.size() > 0 && d.getFirst().compareTo(needed) <=0) {
                            res.add(d.removeFirst());
                        }
                        if (tm.get(needed) > 0) break; // we have more in string
                    }
                }
            } else {
                d.push(curr);
            }
        }



        while(d.size() > 0){
            res.add(d.remove());
        }
        for(Character c: res){
            System.out.print(c);
        }
        System.out.println();

    }
}