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

    public static void main(String args[]){
        Scanner s = new Scanner(System.in);
        String str = s.nextLine();
        int[] alph = new int[26];
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            alph[c-'a']++;
        }
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(i<str.length()){
            char c = str.charAt(i);
            if(stack.isEmpty() || checkForSmall(stack.peek()-'a',alph)){
                stack.push(c);
                alph[c-'a']--;
                i++;
            }else{
               sb.append(stack.pop());
            }
        }

        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        System.out.println(sb.toString());
    }

    static boolean checkForSmall(int c,int[] a){
        for(int i=0;i<c;i++){
            if(a[i]>0){
                return true;
            }
        }
        return false;
    }
}