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
// practice with kaiboy
import java.io.*;
import java.util.*;

public class CF797C extends PrintWriter {
	CF797C() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF797C o = new CF797C(); o.main(); o.flush();
	}

	static final int A = 26;
	int[] kk = new int[A];
	boolean check(byte a) {
		for (int x = 0; x < a - 'a'; x++)
			if (kk[x] > 0)
				return false;
		return true;
	}
	void main() {
		byte[] aa = sc.next().getBytes();
		int n = aa.length;
		for (int i = 0; i < n; i++) {
			byte a = aa[i];
			kk[a - 'a']++;
		}
		int cnt = 0;
		byte[] bb = new byte[n]; int m = 0;
		for (int i = 0; i < n; i++) {
			byte a = aa[i];
			kk[a - 'a']--;
			if (check(a)) {
				bb[m++] = a;
				while (cnt > 0 && check(a = aa[cnt - 1])) {
					cnt--;
					bb[m++] = a;
				}
			} else
				aa[cnt++] = a;
		}
		println(new String(bb));
	}
}
