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.BufferedReader;
import java.util.Stack;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException
	  {
	   InputStreamReader r=new InputStreamReader(System.in);   
	   BufferedReader br=new BufferedReader(r);
	   MinimalString ob=new MinimalString(br);
	   ob.processInput(br.readLine());
	   ob.displayMinimalString();
		
	  }
}
class MinimalString {
   int lim=100000;
   BufferedReader br;
   int N;
   String s;
   MinimalString(BufferedReader br)
   {
	   this.br=br;
   }
   public void processInput(String s)
   {
	   N=s.length();
	   this.s=s;
   }
   public void displayMinimalString()
   {
	  int hash[]=new int[26];
	  char chArr[]=new char[26];
	  for(int i=0;i<N;i++)
	    hash[s.charAt(i)-'a']++;
	  
	  int idx=0;
	  for(int i=0;i<26;i++)
	  {
		  if(hash[i]!=0)
		  {
			  chArr[idx]=(char)('a'+i);
			  idx++;		  
		  }
	  }
	  
	  
	  Stack<Character> st=new Stack<Character>();
	   //now the game starts
	  int j=0; //indexing to chArr[]
	  //we are waiting for character chArr[j]
	  //hash contains the count of chArr[j] in s
	  StringBuilder res=new StringBuilder("");
	  for(int i=0;i<N;i++) {
		  char temp=s.charAt(i);
		  if(temp==chArr[j])
		  {
			  res=res.append(temp);
			  hash[chArr[j]-'a']--;
			  
			  if(hash[chArr[j]-'a']==0 && j+1<idx)
			  {
				  //look at the characters present in stack
				  j=j+1;
				  while(!st.empty())
				  {
			          if(st.peek()<=chArr[j])
			          {
 			        	res=res.append(st.peek());
                        st.pop();			        		  
			        	 
			          }
			          else
			          {
			        	  if(hash[chArr[j]-'a']==0 && j+1<idx)
			        		  j=j+1;
			        	  else
			        		  break;
			          }
				  }
			  }
		  }
		  else
		  {
			  st.push(temp);
			  hash[temp-'a']--;
			  
		  }
		  
	  }
	  
	  while(!st.empty())
		  res=res.append(st.pop());
	  
	  
	  System.out.println(res);
	   
	   
   } 
   
}
