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
//package EDU19;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class C {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		HashMap<Character, Integer> map = new HashMap<>();
		HashMap<Character, Integer> tMap = new HashMap<>();
		LinkedList<Character> s = new LinkedList<Character>();
		for(int i = 0; i < str.length(); i++){
			char c = str.charAt(i);
			s.add(c);
			if(map.containsKey(c)){
				int num = map.get(c);
				map.put(c, ++num);
			}else map.put(c, 1);
		}
		StringBuilder t = new StringBuilder(""), u = new StringBuilder("");
			
		while(!s.isEmpty() || !(t.length() == 0)){
			if(t.length() == 0){
				moveSIntoT(s, t, map, tMap);
			}
			else if(s.isEmpty() && !(t.length() == 0)){
				moveTIntoU(t, u, tMap);
			}
			else{
				char symbInS = s.getFirst();
				char symbInT = t.charAt(t.length() - 1); 
				if(symbInS == symbInT){
					boolean existSmaller = false;
					for(char c = (char) (symbInT - 1); c >= 'a'; c--){
						if(c < symbInT && map.containsKey(c) && map.get(c) > 0){
							existSmaller = true;
							break;
						}
					}
					if(existSmaller) moveSIntoT(s, t, map, tMap);
					else moveTIntoU(t, u, tMap);	
				}
				else if(symbInS < symbInT){
					moveSIntoT(s, t, map, tMap);
				}
				else{
					boolean existSmaller = false;
					for(char c = (char) (symbInT - 1); c >= 'a'; c--){
						if(c < symbInT && map.containsKey(c) && map.get(c) > 0){
							existSmaller = true;
							break;
						}
					}
					if(!existSmaller) moveTIntoU(t, u, tMap);
					else moveSIntoT(s, t, map, tMap);
				}
			}
		}
		System.out.println(u);	
		sc.close();
	}
	public static void moveSIntoT(LinkedList<Character> s, StringBuilder t, HashMap<Character, Integer> map, HashMap<Character, Integer> tMap){
		Character symb = s.getFirst();
		s.removeFirst();
		t.append(symb);
		
		if(map != null){
			int num = map.get(symb);
			map.put(symb, --num);
		}
		
		if(tMap.containsKey(symb)){
			int num = tMap.get(symb);
			tMap.put(symb, ++num);
		}else tMap.put(symb, 1);
	}
	public static void moveTIntoU(StringBuilder t, StringBuilder u, HashMap<Character, Integer> tMap){
		char symb = t.charAt(t.length() - 1);
		t.deleteCharAt(t.length() - 1);
		u.append(symb);
		
		if(tMap != null){
			int num = tMap.get(symb);
			tMap.put(symb, --num);
		}
	}
}
