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

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

    private static void solve(String input) {
        int arr[] = new int[26];
        List<Character> list = new LinkedList<>();
        for (int i = 0; i < input.length(); i++) {
            int pos = input.charAt(i) - 97;
            if (arr[pos] == 0) {
                list.add(input.charAt(i));
            }
            arr[pos] = arr[pos] + 1;
        }

        Collections.sort(list);

        Stack<Character> store = new Stack<>();
        Stack<Character> result = new Stack<>();

        Iterator<Character> iterator = list.iterator();
        char required = iterator.next();

        for (int i = 0; i < input.length(); i++) {
            while (arr[required - 97] == 0 && iterator.hasNext()) {
                required = iterator.next();
            }
            char current = input.charAt(i);
            if (store.isEmpty()) {
                if (current == required) {
                    result.push(current);
                } else {
                    store.push(current);
                }
            } else {
                while (!store.isEmpty() && store.peek() <= required) {
                    result.push(store.pop());
                }
                if (current == required) {
                    result.push(current);
                } else {
                    store.push(current);
                }
            }
            arr[current - 97] = arr[current - 97] - 1;
        }

        while (!store.isEmpty()) {
            result.push(store.pop());
        }

        for (Character character : result) {
            System.out.print(character);
        }
    }
}















