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.ArrayDeque;
public final class Main{
    public static char findNextNonZero(int count[]){
        for(int i=97;i<=122;i++){
            if(count[i]!=0){
                return (char) i;
            }
        }
        return 'z';
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String ip = sc.next();
        ArrayDeque<Character> stck = new ArrayDeque<Character>();
        int count[] = new int[123];
        for(int i=0;i<ip.length();i++){
            char curr = ip.charAt(i);
            count[curr]++;
        }
        char nextLCh = findNextNonZero(count);
        for(int i=0;i<ip.length();i++){
            while(!stck.isEmpty() && (stck.getLast())<=nextLCh){
                System.out.print(stck.removeLast());
            }
            char curr = ip.charAt(i);
            count[curr]--;
            stck.addLast(curr);
            nextLCh = findNextNonZero(count);
        }
        while(!stck.isEmpty()){
            System.out.print(stck.removeLast());
        }
    }
}