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.io.FilterInputStream;
import java.util.Vector;
import java.io.BufferedInputStream;
import java.util.Stack;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CMinimalString solver = new CMinimalString();
        solver.solve(1, in, out);
        out.close();
    }

    static class CMinimalString {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            char[] ar = in.scanString().toCharArray();
            Stack<Character> st = new Stack<>();
            StringBuilder sb = new StringBuilder();
            char[] min = new char[ar.length];
            min[ar.length - 1] = ar[ar.length - 1];
            for (int i = ar.length - 2; i >= 0; i--) min[i] = (char) Math.min(min[i + 1], ar[i]);
            for (int i = 0; i < ar.length; ) {
                if (st.empty()) {
                    while (i < ar.length && min[i] != ar[i]) st.push(ar[i++]);
                    sb.append(ar[i++]);
                } else {
                    if (min[i] < st.peek()) {
                        while (i < ar.length && min[i] != ar[i]) st.push(ar[i++]);
                        sb.append(ar[i++]);
                    } else {
                        sb.append(st.pop());
                    }
                }
            }
            while (st.size() > 0) sb.append(st.pop());
            out.println(sb);
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public String scanString() {
            int c = scan();
            if (c == -1) return null;
            while (isWhiteSpace(c)) c = scan();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return res.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

