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 final class Minimal_String
{
	public static boolean check(int arr[],int index)
	{
		int temp=index;
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]!=0&&i!=index)
			{
				if(i<=temp)
					return false;
			}
		}
		return true;
	}
	public static void main(String[] args)
		{
			Scanner sc=new Scanner(System.in);
			String str=sc.nextLine();
			int arr[]=new int[26];
			for(int i=0;i<str.length();i++)
				arr[str.charAt(i)-'a']++;
			Stack<Character> st=new Stack<Character>();
			StringBuilder u=new StringBuilder("");
			for(int i=0;i<str.length();i++)
			{
				char ch=str.charAt(i);
				boolean flag=check(arr,ch-'a');
				st.push(ch);
				arr[ch-'a']--;
				if(flag==true)
				{
					while(!st.empty()&&check(arr,st.peek()-'a'))
						u.append(st.pop());
				}
			}
			//System.out.println(st);		
			while(!st.empty())
				u.append(st.pop());
			System.out.println(u);
		}
}