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

/**
 * Created by Lenovo on 21-12-2016.
 */
public class z {
    public static ArrayList<ArrayList<String>> ss;
    public  static int visit[];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        String s1=(br.readLine());
        StringBuilder s=new StringBuilder(s1);
        StringBuilder t=new StringBuilder("");
        StringBuilder u=new StringBuilder("");
        int n=s.length();
        int arr[]=new int[26];
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        char g=s.charAt(0);
       // System.out.println(ch);
        int pointer=0;
        for(int i=0;i<26;i++){
            if(arr[i]>0){
                pointer=i;
                break;
            }
        }
        for(int i=0;i<n;i++){
            char c=s.charAt(0);
            s.delete(0,1);
            if(c-'a'==pointer){
                u.append(c);
                arr[pointer]--;
                for(int j=pointer;j<26;j++){
                    if(arr[j]>0){
                        pointer=j;
                        break;
                    }
                }
                if(t.length()!=0&&pointer<26) {
                    if (t.charAt(t.length() - 1)-'a'<=pointer) {
                        while (t.length() > 0) {
                            if (t.charAt(t.length() - 1) -'a'<=pointer) {
                                char x = t.charAt(t.length() - 1);
                                t.delete(t.length() - 1, t.length());
                                u.append(x);
                            } else {
                                break;
                            }
                        }
                    }
                }
            }
            else{
                if(t.length()!=0&&pointer<26) {
                    if (t.charAt(t.length() - 1)-'a'<=pointer) {
                        while (t.length() > 0) {
                            if (t.charAt(t.length() - 1) -'a'<=pointer) {
                                char x = t.charAt(t.length() - 1);
                                t.delete(t.length() - 1, t.length());
                                u.append(x);
                            } else {
                                break;
                            }
                        }
                    }
                }
                arr[c-'a']--;
                t.append(c);
            }
        }
        t.reverse();
        u.append(t);
        System.out.println(u);




    }
    public static int binary_search2(ArrayList<Character> s, int key, int low, int high)
    {
        int middle;

        if (low > high) return (low);
        middle = (low+high)/2;
        if (s.get(middle) < key)
            return( binary_search2(s,key,middle+1,high) );
        else
            return(binary_search2(s,key,low,middle-1) );
    }

}