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 Main {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String string = in.readLine();
        int n = string.length();
        int[] a = new int[n+1];
        int[] count = new int[26];
        for (int i = 1; i <= n; i++) {
            a[i] = string.charAt(i-1)-'a';
            count[a[i]]++;
        }
        Stack<Integer> stack = new Stack<>();
        outer: for (int i = 1; i <= n; i++) {
            stack.push(a[i]);
            count[a[i]]--;
            while (!stack.isEmpty()) {
                int opt = stack.peek();
                for (int j = 0; j < opt; j++) {
                    if (count[j] > 0) {
                        continue outer;
                    }
                }
                out.print((char) (stack.pop() + 'a'));
            }
        }
        while (!stack.isEmpty()) {
            int x = stack.pop();
            out.print((char)(x + 'a'));
        }
        out.print('\n');
        out.close();
    }

}
/*



 */
