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 javafx.util.Pair;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        char[] c = s.toCharArray();
        int[] a = new int[26];
        int n = s.length();
        Stack<Character> st = new Stack<>();
        for(int i=0;i<n;i++){
            a[c[i]-'a']++;
        }
        int ind = 0;
        int x = 0;
        StringBuffer ans = new StringBuffer();
        for(char ch = 'a';ch<='z';ch++) {
            while (st.size() > 0 && st.peek() <= ch) {
                ans.append(st.pop());
            }
            int nextPos = s.indexOf(ch, ind);
            while (nextPos >= 0) {
                while (ind < nextPos) {
                    st.push(s.charAt(ind++));
                }
                ans.append(ch);
                ind++;
                nextPos = s.indexOf(ch, ind);
            }
        }
            while (st.size() > 0){
                ans.append(st.pop());
            }

        while (!st.empty()){
            ans.append(st.pop());
        }

        System.out.println(ans.toString());
    }
}
