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 Minimal
{
	 public static void main(String[] args) {
	 	Scanner sc = new Scanner(System.in);
		StringBuffer s1 = new StringBuffer();
		String ss = sc.nextLine().trim();
		Queue<Character> s = new LinkedList<>();
		int a[] = new int[26];
		for(int i=0;i<ss.length();i++){
			a[(int)ss.charAt(i)-97]++;
			s.add(ss.charAt(i));
		}
		Stack<Character> t = new Stack<Character>();
		while(s.isEmpty()==false)
		{
			if(t.isEmpty()){
				a[(int)s.peek()-97]--;
				t.push(s.remove());
			}
			else{
				boolean f = true;
				for(int i=(int)t.peek()-97-1;i>=0;i--)
						if(a[i]!=0){
							f = false;
							break;
						}
				if(f==true){
					s1.append(t.pop());
				}
				else{
					a[(int)s.peek()-97]--;
					t.push(s.remove());
				}
			}
		}
		while(t.isEmpty()==false)
			s1.append(t.pop());
		System.out.print(s1);
	}
}