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.util.*;

public class Solution {
	static List<String> list = new ArrayList <> ();
	
	public static void greed (StringBuilder s, StringBuilder t, StringBuilder u) {
		if (s.length () > 0) {
			greed (new StringBuilder (s).deleteCharAt (0), new StringBuilder (t).append (s.charAt (0)), new StringBuilder (u));
		} else if (s.length () == 0 && t.length () > 0) {
			u.append (t.reverse ());
			t.setLength (0);
		}
		if (t.length () > 0) {
			greed (new StringBuilder (s), new StringBuilder (t).deleteCharAt (t.length () - 1), new StringBuilder (u).append (t.charAt (t.length () - 1)));
		}
		if (s.length () == 0 && t.length () == 0)
			list.add (u.toString ());
	}
	
	public static void dogreed (String str) {
		StringBuilder s = new StringBuilder (str);
		StringBuilder t = new StringBuilder ();
		StringBuilder u = new StringBuilder ();
		
		greed (s, t, u);
		
		list.sort ((a, b) -> { return a.compareTo (b); });
		
		System.out.println (list.get (0));
	}
	
	public static void other (String str) {
		StringBuilder t = new StringBuilder ();
		StringBuilder u = new StringBuilder ();
		int[] arr = new int[26];
		int dex = 0;
		
		for (int i = 0; i < str.length (); i++) arr[str.charAt (i) - 'a']++;
		
		for (int i = 0; i < str.length (); i++) {
			while (arr[dex] == 0) dex++;
			while (t.length () > 0 && t.charAt (t.length () - 1) - 'a' <= dex) {
				u.append (t.charAt (t.length () - 1));
				t.deleteCharAt (t.length () - 1);
			} 
			if (str.charAt (i) - 'a' == dex) {
				u.append (str.charAt (i));
				arr[dex]--;
			} else {
				t.append (str.charAt (i));
				arr[str.charAt (i) - 'a']--;
			}
		}
		
		u.append (t.reverse ());
		
		System.out.println (u.toString ());
	}
	
	
	public static void main (String[] args) {
		Scanner sc = new Scanner (System.in);
		String str = sc.nextLine ();
		
		other (str);
	}
	
}