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();//input string

			Stack<Character> t=new Stack<>();//t as given in the question

			Stack<Character> u=new Stack<>();//u as given in the question

			int n=s.length;//storing the length of the array

			//to store the minimum value of character possible till that index starting from the last one

			char[] minimumTillThatIndex=new char[n];

			minimumTillThatIndex[n-1]=s[n-1];//last value will be its own minimum(base case)



			//this loop stores the minimum value of character possible in that index starting from the end

			for(int i=n-2;i>=0;--i)

				minimumTillThatIndex[i]=(char)Math.min(minimumTillThatIndex[i+1],s[i]);



			//this is the main loop for the result

			for(int i=0;i<n;++i){

				//store all the values in t into u that are less thant the minimum

				//possible value of the character found at that index

				while(!t.isEmpty() && t.peek()<=minimumTillThatIndex[i])

					u.push(t.pop());

				//if the character at current index equals to the character

				//at the minimum index push it into the u stack

				//else push it into the t stack

				if(s[i]==minimumTillThatIndex[i])

					u.push(s[i]);

				else

					t.push(s[i]);

			}

			//if any residual elements are there in t

			//push it into u stack

			while(!t.isEmpty())

				u.push(t.pop());



			//Print the answer

			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();

	}



}
