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;

public class C {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int size = 0;
        char[] st = new char[s.length()];
        char[] res = new char[s.length()];
        char[] b = new char[s.length()];
        b[s.length() - 1] = s.charAt(s.length() - 1);
        for (int i = s.length() - 2; i >= 0; i--){
            if (s.charAt(i) < b[i + 1]){
                b[i] = s.charAt(i);
            } else {
                b[i] = b[i + 1];
            }
        }
        int ress = 0;
        for (int i = 0; i < s.length(); i++) {
            while (size != 0 && st[size - 1] <= b[i]){
                res[ress++] = st[--size];
            }
            if (s.charAt(i) <= b[i]){
                res[ress++] = s.charAt(i);
            } else {
                st[size++] = s.charAt(i);
            }
        }
        while (size != 0){
            res[ress++] = st[--size];
        }
        System.out.println(new String(res));
    }
}
