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 a{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		StringBuffer s=new StringBuffer(in.next());

		int[] freq=new int[26];

		for(int i=0;i<s.length();i++)
			freq[s.charAt(i)-'a']++;

		StringBuffer sb=new StringBuffer();
		Stack<Character> stack=new Stack<Character>();

		for(int i=0;i<freq.length;i++){

			int j;

			for(j=0;j<s.length()&&freq[i]!=0;j++){

				if(s.charAt(j)-'a'==i){

					while(!stack.isEmpty()&&stack.peek()-'a'<=s.charAt(j)-'a')
						sb.append(stack.pop());

					sb.append(s.charAt(j));
					freq[i]--;
				}
				else{

					while(!stack.isEmpty()&&stack.peek()-'a'<=i)
						sb.append(stack.pop());

					stack.push(s.charAt(j));
					freq[s.charAt(j)-'a']--;

				}
			}

			s=new StringBuffer(s.substring(j,s.length()));
	
		}

		while(!stack.isEmpty()){
			sb.append(stack.pop());
		}

		System.out.print(sb);
		
	}
}
