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.io.*;
import java.util.*;
public final class Minstr
{
	static class Input
	{
		BufferedReader br;
		StringTokenizer st;
		public Input()
		{
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		String next()
		{
			while(st==null||!st.hasMoreElements())
			{
				try
				{
					st=new StringTokenizer(br.readLine());
				}
				catch(IOException e)
				{
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt()
		{
			return Integer.parseInt(next());
		}
		String nextLine()
		{
			String str="";
			try
			{
				str=br.readLine();
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}
			return str;
		}
	}
	public static void main(String[] args)
	{
		Input in=new Input();
		String str=in.nextLine();
		int len=str.length();
		int[] car=new int[26];
		for(int i=0;i<len;i++)
		{
			car[str.charAt(i)-97]++;
		}
		Stack<Character> st=new Stack<Character>();
		int carind=0;
		int i=0;
		while(i<len)
		{
			while(car[carind]!=0&&i<len)
			{
				char ch=str.charAt(i);
				if(ch-97==carind)
				{
					System.out.print(ch);
					car[carind]--;
					i++;
				}
				else
				{
					st.push(ch);
					car[ch-97]--;
					i++;
				}
			}
			carind++;
			while(!st.isEmpty()&&st.peek()-97<=carind)
			{
				System.out.print(st.pop());
			}
		}
		while(!st.isEmpty())
		{
			System.out.print(st.pop());
		}
		System.out.println();
	}
}