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.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

public class C{
	
	static class ProblemSolver{
		public void solveTheProblem(InputReader in,PrintWriter out){
			char[] s=in.next().toCharArray();//taking the input as character array
			int n=s.length;//storing the length of the string
			char[] minimumTillThatIndex=new char[n];//to store the minimum value possible till that index
			minimumTillThatIndex[n-1]=s[n-1];
			for(int i=n-2;i>=0;--i)
				minimumTillThatIndex[i]=(char)Math.min(minimumTillThatIndex[i+1],s[i]);
			Stack<Character> t=new Stack<>();//Variables according to the question
			Stack<Character> u=new Stack<>();//Variables according to the question
			for(int i=0;i<n;++i){
				while(!t.isEmpty() && t.peek()<=minimumTillThatIndex[i])
					u.push(t.pop());
				if(s[i]==minimumTillThatIndex[i])
					u.push(s[i]);
				else
					t.push(s[i]);
			}
			while(!t.isEmpty())u.push(t.pop());
			for(int i=n-1;i>=0;--i)s[i]=u.pop();
			out.print(new String(s));
		}
	}
	
	//Default template for all the codes
	static class InputReader{
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		
		public InputReader(InputStream stream){
			reader=new BufferedReader(new InputStreamReader(stream),32768);
			tokenizer=null;
		}
		
		public String next(){
			while(tokenizer==null || !tokenizer.hasMoreTokens()){
				try{
					tokenizer=new StringTokenizer(reader.readLine());
				}catch(IOException e){
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt(){
			return Integer.parseInt(next());
		}
		
		public long nextLong(){
			return Long.parseLong(next());
		}
		
		public double nextDouble(){
			return Double.parseDouble(next());
		}
		
	}
	
	//Main method for all the codes
	public static void main(String... strings){
		InputStream inputStream=System.in;
		OutputStream outputStream=System.out;
		InputReader in=new InputReader(inputStream);
		PrintWriter out=new PrintWriter(outputStream);
		ProblemSolver problemSolver=new ProblemSolver();
		problemSolver.solveTheProblem(in,out);
		out.close();
	}
	
}