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
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		String s = input.next();
		int n= s.length();
		List<Integer> ans = new ArrayList<>();
		char a[] = new char[n];
		
		int top=-1,x=0,y=-1,z;
		ans.add(n-1);
		x=n-1;
		for(int i=n-2 ;i>=0 ;i--){
		    if(s.charAt(x) - s.charAt(i) >-1){
		        ans.add(i);
		        x=i;
		        
		    }
		}
		Collections.sort(ans);
		
		x=0;
		String you = "";
		you+=s.charAt(ans.get(0));
		
		
    		for(int i= 0;i<n-1;i++){
    		    if(i==ans.get(x)){
    		        if(x!=ans.size()-1){
    		            x++;
    		        }    
    		        if(top>-1){
    		            while(s.charAt(ans.get(x)) - a[top] >-1){
    		                
    		                you +=a[top];
    		                top--;
    		                if(top==-1){
    		                    break;
    		                }
    		            }
    		            
    		        }
    		        you+=s.charAt(ans.get(x));
    		    }
    		    else{
    		        top++;
    		        a[top]=s.charAt(i);
    		    }
    		}
    		
    		while(top>-1){
    		    you+=a[top];
    		    top--;
    		}
    		System.out.println(you);
		
		
		
	}
}
