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.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	public static void main(String[] args) throws Exception {
		String g = br.readLine();
		char[] best = new char[g.length()];
		char lowest = g.charAt(g.length() - 1);
		best[g.length() - 1] = lowest;
		
		for(int i = g.length() - 2; i >= 0; i--) {
			if(g.charAt(i) < lowest)
				lowest = g.charAt(i);
			best[i] = lowest;
		}
		// System.out.println(g);
		// System.out.println(Arrays.toString(best));
		
		Stack<Character> s = new Stack<>();
		Stack<Character> t = new Stack<>();
		StringBuilder u = new StringBuilder();
		
		for(int i = 0; i < g.length(); i++)
			s.push(g.charAt(g.length() - i - 1));
		
		int ind = 0;
		while(s.size() > 0 || t.size() > 0) {
			if(s.size() == 0) {
				// System.out.println("pushed " + t.peek() + " into u");
				u.append(t.pop());
			}
			else if(t.size() == 0) {
				// System.out.println("pushed " + s.peek() + " into t");
				t.push(s.pop());
				ind++;
			}
			else {
				char fromS = best[ind];
				char fromT = t.peek();
				// System.out.println(">> " + fromS);
				// System.out.println(">> " + fromT);
				// System.out.println("---");
				
				if(fromS < fromT) {
					t.push(s.pop());
					ind++;
				}
				else {
					// System.out.println("pushed " + t.peek() + " into u");
					u.append(t.pop());
				}
			}
		}
		pw.println(u.toString());
		
		pw.close();
	}
}
