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.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

public class CF797C {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] in = sc.next().toCharArray();
		ArrayList<C> sorted = new ArrayList<>();
		LinkedList<Character> s = new LinkedList<>();
		Stack<Character> t = new Stack<>();
		StringBuilder u = new StringBuilder();
		for(int i=0; i<in.length; i++) {
			s.add(in[i]);
			sorted.add(new C(in[i], i));
		}
		Collections.sort(sorted);
		C smallest = sorted.get(0);
		for(int i=0; i<=smallest.o_index; i++) t.push(s.poll());
		u.append(t.pop());
		for(int i=1; i<sorted.size(); i++) {
			if(sorted.get(i).o_index>smallest.o_index) {
				while(!t.isEmpty() && t.peek()<=sorted.get(i).val) u.append(t.pop());
				for(int j=smallest.o_index+1; j<=sorted.get(i).o_index; j++) t.push(s.poll());
				u.append(t.pop());
				smallest = sorted.get(i);
			}
		}
		while(!t.isEmpty()) u.append(t.pop());
		System.out.println(u.toString());
	}
	
	static class C implements Comparable<C> {
		char val;
		int o_index;
		
		public C(char val, int o_index) {
			 this.val = val;
			 this.o_index = o_index;
		}

		@Override
		public int compareTo(C o) {
			if(this.val==o.val) return Integer.compare(this.o_index, o.o_index);
			return Integer.compare(this.val, o.val);
		}
	}
}
