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 ProbC {
	public static void main(String[] args) {
		ProbC sol = new ProbC();
		sol.start();
	}

	StringBuffer printstr;

	public void print(Object o){ System.out.print(o); }
	public void println(Object o) { System.out.println(o); }

	public void bufp(Object o){ printstr.append(o); }
	public void bufpl(Object o){ printstr.append(o).append('\n'); }
	public void bufpl() { printstr.append('\n'); }
	public void bufp(char[] c, int offset, int len){ printstr.append(c, offset, len); }
	public void bufpl(char[] c, int offset, int len){ printstr.append(c, offset, len).append('\n'); }

	public void start(){
		submit();
	}
	
	public void submit(){
	try{
		printstr = new StringBuffer();
		Scanner scan = new Scanner(System.in);
		BufferedReader rdr = new BufferedReader(new InputStreamReader(System.in));
		String s = rdr.readLine();
		scan.close();
		
		minstr(s);
		System.out.println(printstr);
		System.out.flush();
	}
	catch(Exception e){}
	}
	
	public void minstr(String str){
		Stack<Character> s = new Stack();
		Stack<Character> min = new Stack();
		Stack<Character> t = new Stack();
		char minch = (char)('z' + 1);
		char[] c = str.toCharArray();
		int n = c.length;
		for(int i=n-1;i>=0;i--){
			if(c[i]<minch) minch = c[i];
			min.push(minch);
			s.push(c[i]);
		}
		char[] u = new char[n];
		for(int i=0;i<n;i++){
			if(s.size()==0) u[i] = t.pop();
			else if(t.size()==0) {
				t.push(s.pop());
				min.pop();
				i--;
			}
			else if(t.peek()<=min.peek()) u[i] = t.pop();
			else{
				t.push(s.pop());
				min.pop();
				i--;
			}
		}
		
		bufpl(new String(u));
	}
}