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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solution {
	public static void main(String[] args) throws java.lang.Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		char[] s = in.readLine().trim().toCharArray();
		int[] arr = new int[26];
		for (int i = 0; i < s.length; i++)
			arr[s[i] - 'a'] += 1;
		Stack<Character> stack = new Stack<>();

		for (Character c : s) {
			stack.add(c);
			arr[c - 'a'] -= 1;
			while (!stack.isEmpty() && stack.peek() <= minimal(arr))
				System.out.print(stack.pop());
		}
		while (!stack.isEmpty())
			System.out.print(stack.pop());
		System.out.println();
		in.close();
	}

	private static Character minimal(int[] arr) {
		for (int i = 0; i < 26; i++)
			if (arr[i] > 0)
				return (char) (i + 'a');
		return (char) ('a' - 1);
	}

	private long gcd(long a, long b) {
		if (a == 0 || b == 0)
			return a + b;
		if (a > b)
			return gcd(a % b, b);
		return gcd(a, b % a);
	}

	private boolean[] seive(int n) {
		boolean[] arr = new boolean[n + 1];
		for (int i = 2; i <= n; i++) {
			if (!arr[i]) {
				int j = i * i;
				for (; j <= n; j += i)
					arr[j] = true;
			}
		}
		return arr;
	}

	private static int[] readInt1DArray(BufferedReader rd) throws Exception {
		String[] ss = rd.readLine().trim().split(" ");
		int[] arr = new int[ss.length];
		for (int i = 0; i < ss.length; i++)
			arr[i] = toInt(ss[i]);
		return arr;
	}

	private static int[][] readInt2DArray(BufferedReader rd, int n)
			throws Exception {
		int[][] arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			String s = rd.readLine();
			for (int j = 0; j < n; j++)
				arr[i][j] = s.charAt(j) - '0';
		}
		return arr;
	}

	private static int toInt(String s) {
		return Integer.parseInt(s);
	}

	private static long toLong(String s) {
		return Long.parseLong(s);
	}
}
