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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.io.IOException;
import java.util.Deque;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author dpark3542
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            char[] a = in.next().toCharArray();
            int n = a.length;
            int[] min = new int[n];
            min[n - 1] = n - 1;
            char cur = a[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                if (a[i] < cur) {
                    min[i] = i;
                    cur = a[i];
                } else {
                    min[i] = min[i + 1];
                }
            }
            StringBuilder sb = new StringBuilder();
            Deque<Character> st = new ArrayDeque<>();
            for (int i = 0; i < n; i = min[i] + 1) {
                while (!st.isEmpty() && st.peekLast() <= a[min[i]]) {
                    sb.append(st.pollLast());
                }
                for (int j = i; j <= min[i]; j++) {
                    if (a[j] != a[min[i]]) {
                        st.addLast(a[j]);
                    } else {
                        sb.append(a[j]);
                    }
                }
            }
            while (!st.isEmpty()) {
                sb.append(st.pollLast());
            }
            out.println(sb);
        }

    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

    }
}

