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.*;
 
public class ms {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[] ary = new int[127];
		String s = in.nextLine();
		
		for ( int i = 0; i < s.length(); i++ ) {
			ary[s.charAt(i)]++;
		}
		
		Stack<Character> st = new Stack<>();
		StringBuilder sb = new StringBuilder();
		
		for ( int i = 0; i < s.length(); i++ ) {
			char c = s.charAt(i);
			st.push(c);
			ary[st.peek()]--;
			while( !st.empty() && isGreater(st.peek(),ary) ) {
				sb.append(Character.toString(st.pop()));
			}
		}
	
		System.out.println(sb.toString());
	}
	
	public static boolean isGreater(char c, int[] ary) {
		
		for ( int i = 64; i < c; i++) {
			if (ary[i] != 0)
				return false;
		}
		return true;
	}
}