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

public class Main {
    public Main() throws IOException {
    }

    static void solve() throws IOException {
//        String s = input.readLine();
        StringBuilder s = new StringBuilder(input.readLine());
        int n = s.length();
        int minPos[] = new int[n]; // store the position of "min character" for i to n
        minPos[n - 1] = n - 1;
        int i = n - 2;
        while (i >= 0) {
            if ((int)s.charAt(i) <= (int)s.charAt(minPos[i + 1])) {
                minPos[i] = i;
            } else {
                minPos[i] = minPos[i + 1];
            }
            i--;
        }

        int pointer = minPos[0];
        StringBuilder leftChars = new StringBuilder(s.substring(0, pointer));
        ans.append(s.charAt(pointer));

        while (pointer < n) {
            if (pointer == n - 1) {
                ans.append(leftChars.reverse());
                break;
            }

            int leftLen = leftChars.length();
            char leftChar = leftLen > 0 ? leftChars.charAt(leftLen - 1) : ('z' + 1);
            int rightCharPos = minPos[pointer + 1];
            char rightChar = s.charAt(rightCharPos);
            if (leftChar <= rightChar) {
                ans.append(leftChar);
                leftChars.deleteCharAt(leftLen - 1);
            } else {
                leftChars.append(s.substring(pointer + 1, rightCharPos));
                ans.append(s.charAt(rightCharPos));
                pointer = rightCharPos;
            }
        }

        output.write(ans.toString());
        output.flush();
        output.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }


    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder ans = new StringBuilder();
    static StringTokenizer stringTokenizer;

    static int ni1() throws IOException {
        return Integer.parseInt(input.readLine());
    }

    static int ni2() throws IOException {
        return Integer.parseInt(stringTokenizer.nextToken());
    }

    static long nl1() throws IOException {
        return Long.parseLong(input.readLine());
    }

    static long nl2() {
        return Long.parseLong(stringTokenizer.nextToken());
    }

    static String ns() {
        return stringTokenizer.nextToken();
    }

    static void rl() throws IOException {
        stringTokenizer = new StringTokenizer(input.readLine());
    }
}