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.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * Created by sbabkin on 9/14/2015.
 */
public class SolverC {

    public static void main(String[] args) throws IOException {
        new SolverC().Run();
    }

    BufferedReader br;
    PrintWriter pw;
    StringTokenizer stok;

    private String nextToken() throws IOException {
        while (stok==null || !stok.hasMoreTokens()){
            stok = new StringTokenizer(br.readLine());
        }
        return stok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private void Run() throws IOException {
//        br=new BufferedReader(new FileReader("input.txt"));
//        pw=new PrintWriter("output.txt");
        br=new BufferedReader(new InputStreamReader(System.in));
        pw=new PrintWriter(new OutputStreamWriter(System.out));

        solve();
        pw.flush();
        pw.close();
    }
    
    String str;
    int[] kol = new int[26];
    int len;
    List<Integer> result = new ArrayList<>();

    private void solve() throws IOException {
        str=br.readLine();
        len=str.length();
        for (int i=0; i<len; i++) {
            kol[(int)str.charAt(i)-(int)'a']++;
        }
        Stack<Integer> stack = new Stack<>();
        int pos = 0;
        for (int i=0; i<26; i++) {
            if (kol[i]>0 || (!stack.isEmpty() && stack.peek() <= i)) {
                while (!stack.isEmpty() && stack.peek() <= i) {
                    result.add(stack.pop());
                }
                while (kol[i]>0) {
                    if ((int)str.charAt(pos)-(int)'a'==i) {
                        result.add(i);
                    } else {
                        stack.add((int)str.charAt(pos)-(int)'a');
                    }
                    kol[(int)str.charAt(pos)-(int)'a']--;
                    pos++;
                }
            }
        }
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        result.forEach(num -> pw.print((char)((int)'a' + num)));
        pw.println();
    }

}
