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
//codeforces_797C
import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import static java.lang.Math.*;
import java.math.*;

public class Main{

	static PrintWriter go = new PrintWriter(System.out);

	public static void main(String args[]) throws IOException,FileNotFoundException {
		BufferedReader gi = new BufferedReader(new InputStreamReader(System.in));
		char[] s = gi.readLine().toCharArray();
		Stack<Character> t = new Stack<>();
		Stack<Character> u = new Stack<>();
		int[] occ = new int[300];
		for ( char c : s ){ occ[c]++; }
		int x = 'a';
		for ( int k = 0; k < s.length; k++ ){
			while ( x <= 'z' && occ[x] == 0 ){ x++; }
			while ( !t.isEmpty() && t.peek() <= x ){
				u.push(t.pop());
			}
			if ( s[k] == x ){
				u.push(s[k]);
				occ[x]--;
			}
			else{
				t.push(s[k]);
				occ[s[k]]--;
			}
		}
		while ( !t.isEmpty() ){ u.push(t.pop()); }
		for (char c : u){ go.print(c); }go.println();
		go.close();

	}

	static int[] parseArray(BufferedReader gi) throws IOException{
		String[] line = gi.readLine().split(" ");
		int[] rez = new int[line.length];
		for ( int k = 0; k < line.length; k++){
			rez[k] = Integer.parseInt(line[k]);
		}
		return rez;
	}
}