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.Stack;

public class Test {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Test test = new Test();
        String string = reader.readLine();
        System.out.println(test.getMinimalString(string));
    }

    private String getMinimalString(String string) {
        if(string == null || string.length() == 0)
            return string;
        int min = Integer.MAX_VALUE;
        int[] array = new int[string.length()];
        for(int i=string.length()-1; i>=0; i--) {
            if(min > string.charAt(i)) {
                min = string.charAt(i);
            }
            array[i] = min;
        }

        Stack<Character> stack = new Stack<>();
        StringBuilder u = new StringBuilder();
        int ptr = 0;
        while (ptr < string.length()) {
            while ((array[ptr] != string.charAt(ptr)) && (ptr < string.length())) {
                stack.push(string.charAt(ptr));
                ptr++;
            }
            if(ptr == string.length()) {
                break;
            }
            u.append(string.charAt(ptr));
            ptr++;

            if(ptr == string.length()) {
                break;
            }

            while (!stack.isEmpty() && (stack.peek().charValue() <= array[ptr])) {
                u.append(stack.pop());
            }
        }
        while (!stack.isEmpty()) {
            u.append(stack.pop());
        }
        return u.toString();

    }
}