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.*;

import static java.lang.StrictMath.min;

public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out, true);
        String s = in.next();
        int l = s.length();
        char[] minV = new char[l];
        minV[l - 1] = s.charAt(l - 1);
        for (int i = l - 2; i >= 0; i--){
            minV[i] = s.charAt(i);
            if (minV[i] > minV[i + 1])
                minV[i] = minV[i + 1];
        }

        Stack<Integer> stk = new Stack<>();
        stk.push(0);
        StringBuilder res = new StringBuilder();

        /*boolean[] used = new boolean[l];
        used[0] = true;
        while (!stk.empty()){
            int cur = stk.peek();
            char c1 = s.charAt(cur);
            char c2 = 'z' + 1;
            if (cur < l - 1)
                c2 = minV[cur + 1];
            if (c2 <= c1){
                stk.push(cur + 1);
                used[cur + 1] = true;
            }else{
                res.append(c1);
                stk.pop();
            }
        }*/

        int pos = -1;
        boolean[] used = new boolean[l];
        used[0] = true;
        int ptr = 1;
        while (!stk.empty()) {
            pos = stk.peek();
            char ch1 = s.charAt(pos);
            char ch2 = 'z' + 1;
            if (ptr < l)
                ch2 = minV[ptr];
            if (ch2 < ch1 && !used[ptr]) {
                stk.push(ptr);
                used[ptr] = true;
                ++ptr;
            }
            else {
                res.append(ch1);
                stk.pop();
                if (stk.empty() && ptr < l){
                    stk.push(ptr);
                    used[ptr] = true;
                    ++ptr;
                }
            }
        }

        out.print(res);
        out.close();
    }
}