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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package pkg21.days.of.code;

/**
 *
 * @author Pravash Ranjan
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class MinimalStringCF {
    static 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;
        }
    }
    public static void main(String args[])
    {
        FastReader ob=new FastReader();
        String s=ob.nextLine();
        Stack<Character> t=new Stack<>();
        StringBuilder ans=new StringBuilder("");
        int a[]=new int[26];
        for(int i=0;i<26;i++)
            a[i]=-1;
        for(int i=0;i<s.length();i++)
            a[s.charAt(i)-'a']=i;
        int pos=0;
        for(int i=0;i<26;i++)
        {
            if(a[i]!=-1)
            {
                while(!t.empty() && t.peek()<=(char)(i+97))
                    ans.append(t.pop());
                while(pos<=a[i])
                {
                    if(s.charAt(pos)-'a'==i)
                        ans.append((char)('a'+i));
                    else
                        t.push(s.charAt(pos));
                    pos++;
                }
            }
        }
        while(!t.empty())
            ans.append(t.pop());
        System.out.println(ans);
        
    }
    
}
