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 MinimalString {
	public MinimalString(Scanner scan, BufferedReader br, PrintWriter out) throws Exception {
		char[] c = br.readLine().toCharArray();
		int[] a = new int[26];
		Arrays.fill(a, -1);
		TreeSet<Integer>[] set = new TreeSet[26];
      	for(int i = 0 ; i < 26 ; i++)
        	set[i] = new TreeSet<>();
		for(int i = 0 ; i < 26 ; i++)
			for(int j = 0 ; j < c.length ; j++)
				if(c[j]-'a' == i)
					set[i].add(j);
		boolean[] taken = new boolean[c.length];
		StringBuilder res = new StringBuilder();
		Stack<Character> s = new Stack<>();
		int id = 0;
		for(int i = 0 ; i < 26 ; i++) {
			while(!s.isEmpty() && s.peek()-'a' <= i) {
				res.append(s.pop());
			}
			if(set[i].size() > 0) {
                        while(set[i].ceiling(id) != null) {
				      s.add(c[id++]);
                              if(s.peek()-'a' == i)
                                    res.append(s.pop());
			      }
			}
		}
		while(!s.isEmpty())
			res.append(s.pop());
		out.println(res);
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner scan = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		new MinimalString(scan, br, out);
		out.close();
	}
}