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

public class MinimalString {
	
 public static void main(String[] args){
	Scanner scan  = new Scanner(System.in);
	
	
	char[] arr = scan.next().toCharArray();
	 
	char[] min = new char[arr.length];
	
	int n  = arr.length;
	min[n - 1] = arr[n-1];
	
	
	for(int i = n-2; i >= 0 ; --i){
		min[i] = (char)Math.min(arr[i], min[i+1]);
	}
//	System.out.println(Arrays.toString(min));
//	System.out.println(String.valueOf(arr));
	
	
	Stack<Character> s = new Stack<>();
    StringBuilder res = new StringBuilder();
    
    for (int i = 0; i < n; i++) {
        if (s.isEmpty() || min[i] < s.peek()) s.push(arr[i]);
        else {
            --i;
            res.append(s.pop());
        }
    }
    while (!s.isEmpty())
        res.append(s.pop());
    
    	System.out.println(res);
    	
 }
}
