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
/* package codechef; // don't place package name! */

import java.lang.*;
import java.io.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader sc = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		String s = sc.next();
		Stack<Integer> st = new Stack<>();
		String output = new String();
		int alphaPtr=0,sPtr=0;
		
		TreeSet<Integer> set[] = new TreeSet[26];
		for(int i=0;i<26;i++) set[i]=new TreeSet<>();
		for(int i=0;i<s.length();i++) set[(int)s.charAt(i)-97].add(i);
		//out.println(s.length());
		//out.println("b "+set[1]);
		while(alphaPtr<26)
		{
		    while(!st.isEmpty() && st.peek()<=alphaPtr) output+=(char)(st.pop()+97);
		    //out.println("Why not here");
		    for(int index:set[alphaPtr])
		    {
		        if(index>=sPtr) {
		            //out.println(index);
		            output+=(char)(alphaPtr+97);
		        for(int i=sPtr;i<index;i++) st.push((int)s.charAt(i)-97);
		        sPtr=index+1;
		        }
		    }
		    if(sPtr>=s.length()) break;
		    alphaPtr++;
		}
		while(!st.isEmpty()) output+=(char)(st.pop()+97);
		out.println(output);
		out.close();
	}
}

class FastReader 
{ 
    BufferedReader br; 
    StringTokenizer st; 
 
    public FastReader() 
    { 
        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()); 
    } 
 
    long nextLong() 
    { 
        return Long.parseLong(next()); 
    } 
 
    double nextDouble() 
    { 
        return Double.parseDouble(next()); 
    } 
 
    String nextLine() 
    { 
        String str = ""; 
        try
        { 
            str = br.readLine(); 
        } 
        catch (IOException e) 
        { 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}