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.security.SecureRandom;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;

public class C {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
//		while(true){
//			Random rnd = new Random();
//			String str = randomString(rnd.nextInt(1000) + 500);
//			System.out.println("INPUT - " + str);
			HashMap<Character, Integer> map = new HashMap<>();
			HashMap<Character, Integer> tMap = new HashMap<>();
			LinkedList<Character> s = new LinkedList<Character>();
			LinkedList<Character> copyS = new LinkedList<Character>();
			for(int i = 0; i < str.length(); i++){
				char c = str.charAt(i);
				s.add(c);
				copyS.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(""), copyT = new StringBuilder("");
	//		StringBuilder allLetters =  new StringBuilder("abcdefghijklmnopqrstuvwxyz");
			
	//		moveSIntoT(s, t);
	//		moveSIntoT(s, t);
	//		moveSIntoT(s, t);
	//		
	//		moveTIntoU(t, u);
	//		moveTIntoU(t, u);
	//		
	//		System.ouabcbabbcct.println(s + " : " + t + " : " + u);
			
			while(!s.isEmpty() || !(t.length() == 0)){
	//			System.out.println("S - " + s);
				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){
						//move decision
						boolean existSmaller = false;
//						char smallest = symbInS;
//						for(char c = (char) (symbInS - 1); c >= 'a'; c--){
//							if(c < symbInS && tMap.containsKey(c) && tMap.get(c) > 0 && smallest > c){
//								smallest = c;
//							}
//						}
						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;
	//					Change using hash table
	//					for(int i = 0; i < s.size(); i++){
	//						symbInS = s.get(i);
	//						if(symbInS < symbInT){
	//							existSmaller = true;
	//							break;
	//						}
	//					}
						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);
					}
				}
			}
//			StringBuilder slowResult = slow(copyS, copyT);
//			if(!u.toString().equals(slowResult.toString())){
//				System.out.println("ERROR");
//				System.out.println(u);
//				System.out.println(slowResult);
//				break;
//			}
//			else{
//				System.out.println(u);
//				System.out.println(slowResult);
//			}
			System.out.println(u);
//		}
		sc.close();
	}
	
//	public static StringBuilder slow(LinkedList<Character> s, StringBuilder t){
//		StringBuilder u = new StringBuilder("");
//		while(!s.isEmpty() || !(t.length() == 0)){
////			System.out.println("S - " + s);
//			if(t.length() == 0){
//				moveSIntoT(s, t, null);
//			}
//			else if(s.isEmpty() && !(t.length() == 0)){
//				moveTIntoU(t, u);
//			}
//			else{
//				char symbInS = s.getFirst();
//				char symbInT = t.charAt(t.length() - 1); 
//				if(symbInS == symbInT){
//					moveSIntoT(s, t, null);
//				}
//				else if(symbInS < symbInT){
//					moveSIntoT(s, t, null);
//				}
//				else{
//					boolean existSmaller = false;
////					Change using hash table
//					for(int i = 0; i < s.size(); i++){
//						symbInS = s.get(i);
//						if(symbInS < symbInT){
//							existSmaller = true;
//							break;
//						}
//					}
//					if(!existSmaller) moveTIntoU(t, u);
//					else moveSIntoT(s, t, null);
//				}
//			}
//		}
//		return u;
//	}
	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);
		}
	}
	private static String randomString( int len ){
        String AB = "abcdefghijklmnopqrstuvwxyz";
        SecureRandom rnd = new SecureRandom();
        StringBuilder sb = new StringBuilder( len );
        for( int i = 0; i < len; i++ ) 
            sb.append( AB.charAt( rnd.nextInt(AB.length()) ) );
        return sb.toString();
    }
}
