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.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
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) {
//after observing a little it can be seen that it's necessary to pre-calculate
//the minimum char to right of some idx(after popping one)
//so let's use dp for this
			char[] str = in.next ().toCharArray ();
			int len = str.length;
			char[] mn = new char[len+5];
			mn[len] = 'z'+1;
			int[] midx = new int[len+5];
			for (int i = len-1; i>=0; i--) {
				if (str[i]<=mn[i+1]) {
					mn[i] = str[i];
					midx[i] = i;
				}
				else {
					mn[i] = mn[i+1];
					midx[i] = midx[i+1];
				}
			}
//the algorithm will be something like every step either pop or push to the midx[idx+1]
			Stack<Character> stack = new Stack<Character> ();
			int cidx = -1;/*midx[0];
		out.print (str[cidx]);
	    for (int i = 0; i<cidx; i++) {
		    stack.push (str[i]);
	    }*/
			while (cidx<len-1) {
				while (!stack.empty () && stack.peek ()<=mn[cidx+1]) {
					out.print (stack.peek ());
					stack.pop ();
				}
				for (int i = cidx+1; i<=midx[cidx+1]; i++) {
					stack.push (str[i]);
				}
				cidx = midx[cidx+1];
			}
			while (!stack.empty ()) {
				out.print (stack.peek ());
				stack.pop ();
			}
		}
		
	}
	
	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		
		public InputReader (InputStream stream) {
			reader = new BufferedReader (new InputStreamReader (stream), 32768);
			tokenizer = null;
		}
		
		public String next () {
			while (tokenizer == null || !tokenizer.hasMoreTokens ()) {
				try {
					String str;
					if ((str = reader.readLine ()) != null) tokenizer = new StringTokenizer (str);
					else return null;//to detect eof
				} catch (IOException e) {
					throw new RuntimeException (e);
				}
			}
			return tokenizer.nextToken ();
		}
		
	}
}

