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 com.sun.security.auth.UnixNumericGroupPrincipal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

// Class name should be "Source",
// otherwise solution won't be accepted
public class CodeForces {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer=new StringTokenizer(br.readLine());
        String s=tokenizer.nextToken();
        int n=s.length();
        Stack<Character> st=new Stack<>();
        StringBuilder sb=new StringBuilder();
        int[] f=new int[26];

        for (int i=0;i<n;i++){
            f[s.charAt(i)-'a']++;
        }

        for (int i=0;i<n;i++) {
            Character minChar=findNextMinChar(f);
            if(st.empty())
            {
                char now = s.charAt(i);
                f[now-'a']--;
                st.push(now);
            }
            else
            {
                if(minChar!=null && st.peek()<=minChar)
                {
                    char top = st.peek();
                    st.pop();
                    sb.append(top);
                    i--;
                }
                else
                {
                    char now = s.charAt(i);
                    f[now-'a']--;
                    st.push(now);
                }
            }
        }

        while(!st.isEmpty()) {
            sb.append(st.pop());
        }

        System.out.println(sb);
    }

    private static Character findNextMinChar(int []c){

        for (int i = 0; i < c.length; i++) {
            if (c[i]>0){
                return (char) (i+'a');
            }
        }
        return null;
    }
}
