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

public class CF {

	long mod = (long) 1e9 + 7;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int n = s.length();
		char[] arr = s.toCharArray();
		char[] suffMin = new char[n];
		suffMin[n - 1] = arr[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			suffMin[i] = (char) Integer.min(suffMin[i + 1], arr[i]);
		}
		Stack<Character> t = new Stack<>();
		Stack<Character> u = new Stack<>();
		String ans = "";
		for (int i = 0; i < n; i++) {
			while (!t.empty() && t.peek() <= suffMin[i]) {
				u.push(t.pop());
			}
			if (arr[i] == suffMin[i])
				u.push(arr[i]);
			else
				t.push(arr[i]);

		}
		while (!t.empty())
			u.push(t.pop());
		for(int i=n-1;i>=0;--i)
			arr[i]=u.pop();
		System.out.println(new String(arr));
	}
}
