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

public class Main {

    public static void main(String[] args) throws Exception {
        /*797C*/
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        List<Integer> lastExistOfLetter = new ArrayList<>();
        for (int i = 0; i < 130; i++) {
            lastExistOfLetter.add(-1);
        }
        for (int i = 0; i < s.length(); i++) {
            lastExistOfLetter.set(s.charAt(i), i);
        }

        StringBuilder t = new StringBuilder();
        StringBuilder u = new StringBuilder();
        int shiftS = 0;
        while (shiftS <s.length())
        {
            char minInS = findMin(shiftS, lastExistOfLetter);
            if (t.length() > 0 && minInS >= t.charAt(t.length() - 1))
            {
                u.append(t.charAt(t.length() - 1));
                t.deleteCharAt(t.length() - 1);
            }
            else
            {
                while (s.charAt(shiftS) > minInS)
                {
                    t.append(s.charAt(shiftS));
                    shiftS++;
                }
                t.append(s.charAt(shiftS));
                shiftS++;
            }
        }
        for (int i = 0; i < t.length(); i++) {
            u.append(t.charAt(t.length() - i - 1));
        }
        System.out.println(u);
    }

    public static char findMin(int shift, List <Integer> lastExist)
    {
        Character min = null;
        char cur = 'a';
        while (min == null)
        {
            if (lastExist.get(cur) >= shift)
            {
                min = cur;
            }
            else
                cur++;
        }
        return min;
    }
}