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.util.Scanner;
import java.util.Stack;

public class MinimalString {
    public static void main(String[] args)
    {
        /*
        s is the input string
        t and u are empty strings
        possible moves - sFirst to tLast & tLast to uLast
        lexicographically minimal string

         s  = cab;
        ->t = "" ; u = "";
        ->t = c ; u = "";
        ->t = ca ; u = "";
        ->t = c ; u = a;
        ->t = cb ; u = a;
        ->t = c ; u = ab;
        ->t = "" ; u = abc;

       -find the lexicographically minimal character
       //make the string into char array and sort it lexicographically

         */
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        Stack<Character> t = new Stack();
        StringBuilder result = new StringBuilder();
        int idx = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            while ((t.size() > 0) && (t.peek() <= c)) {
                result.append(t.pop());
            }
            int nextPos = s.indexOf(c, idx);
            while (nextPos >= 0) {
                while (idx < nextPos) {
                    t.push(s.charAt(idx++));
                }
                result.append(c);
                idx++;
                nextPos = s.indexOf(c, idx);
            }
        }
        while (t.size() > 0) {
            result.append(t.pop());
        }
        System.out.println(result.toString());
    }

}