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.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main {
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String str = st.nextToken();
		int n = str.length();
		int[] s = new int[n];
		for (int i=0 ; i <n ; i++) s[i] = str.charAt(i);
		int[] counts = new int[255];
		int[] t = new int[n];
		StringBuilder u = new StringBuilder();
		int tPter = 0;
		for (int i=0 ; i<n ; i++) counts[s[i]]++;
		int left = Integer.MAX_VALUE;
		int right = -1;
		for (int i='a' ; i<='z' ; i++) if (counts[i] != 0) {
			right = i;
			break;
		}
		for (int i=0 ; i<n ; i++) {
			if (right<left) {
				if (s[i] != right) {
					t[tPter++] = s[i];
					left = Integer.MAX_VALUE;
					if (tPter != 0) left = t[tPter-1];
					counts[s[i]]--;
					continue;
				}
				//System.out.print((char)s[i]);
				u.append((char)s[i]);
				counts[s[i]]--;
				for (int j=right ; j<='z' ; j++) if (counts[j]!=0) {
					right = j;
					break;
				}
				continue;
			}
			i--;
			u.append((char)t[--tPter]);
			//System.out.print((char)t[--tPter]);
			left = Integer.MAX_VALUE;
			if (tPter != 0) left = t[tPter-1];
		}
		while (tPter>0) u.append((char)t[--tPter]);//System.out.print((char)t[--tPter]);
		System.out.println(u.toString());
	}
}