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

/* Name of the class has to be "Main" only if the class is public. */
public class Solution {
	public static void main(String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str = br.readLine().trim();
		int n = str.length();
		char minFromLeft[] = new char[n];
		minFromLeft[n - 1] = str.charAt(n - 1);
		for (int i = n - 2; i >= 0; i--) {
			if (str.charAt(i) < minFromLeft[i + 1])
				minFromLeft[i] = str.charAt(i);
			else
				minFromLeft[i] = minFromLeft[i + 1];
		}
		char ans[] = new char[n];
		int k = 0;
		Stack<Character> st = new Stack<>();
		for (int i = 0; i < n; i++) {
			st.push(str.charAt(i));
			while (!st.isEmpty() && (i + 1) < n && st.peek().compareTo(minFromLeft[i + 1]) <= 0) {
				ans[k++] = st.pop();
			}
		}
		while (!st.isEmpty()) {
			ans[k++] = st.pop();
		}
		bw.write(String.valueOf(ans));
		bw.flush();
	}
}
