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.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] counts = new int[26];
        for(int i = 0; i < s.length(); i++){
            counts[s.charAt(i) - 'a']++;
        }

        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j < counts.length; j++){
                if(!stack.isEmpty() && (stack.peek()-'a') == j){
                    sb.append(stack.pop());
                    i--;
                    break;
                }
                if(counts[j] == 0){
                    continue;
                }
                counts[s.charAt(i)-'a']--;
                if(j == (s.charAt(i) - 'a') || (!stack.isEmpty() && (j == (stack.peek()- 'a')))){
                    if(j == (s.charAt(i) - 'a'))
                        sb.append(s.charAt(i));
                    else{
                        sb.append(stack.pop());
                        i--;
                        counts[s.charAt(i)-'a']++;
                    }
                }else{
                    stack.push(s.charAt(i));
                }
                break;
            }
        }
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        System.out.println(sb.toString());
    }
}
