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;

public class main {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		StringBuffer s = new StringBuffer();
		StringBuffer t = new StringBuffer();
		StringBuffer u = new StringBuffer();
		char min;
		char maxofmin='a';
		int min_num;
		s.append(input.nextLine());

		while(s.length() != 0){
			if(t.length() == 0){
				t.append(s.charAt(0));
				s.deleteCharAt(0);
			}else{
				min = t.charAt(t.length()-1);
				min_num = s.length();
				for(int n = 0; n < s.length(); n++){
					if(s.charAt(n) < min){
						min = s.charAt(n);
						min_num = n;
					}
					if(maxofmin == min){
						break;
					}
				}
				maxofmin = min;
				if(min_num == s.length()){
					u.append(t.charAt(t.length()-1));
					t.deleteCharAt(t.length()-1);
				}else{
					t.append(s.substring(0, min_num+1));
					s.delete(0,min_num+1);
					u.append(t.charAt(t.length()-1));
					t.deleteCharAt(t.length()-1);
				}
			}
			
		}
		u.append(t.reverse());
		System.out.println(u);
	}
}
