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.*;
import java.lang.*;
import java.io.*;

/*
 * 
 * Comments Here
 * 
 */
public class C19_redo
{
	static BufferedReader br; 
	static BufferedWriter bw; 
	static StringTokenizer st;

	static int n;
	
	public static void main(String[] args) throws java.lang.Exception
	{
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//Uncomment to read from file
    	/*/
    	File file = new File("src/in.txt");
		try {
			in = new Scanner(file);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		/**/
		
		char[] chars = br.readLine().toCharArray();
		n = chars.length;
		ArrayList<Character> s = new ArrayList<Character>();
		for(char c : chars) {
			s.add(c);
		}
		ArrayList<Character> t = new ArrayList<Character>();
		ArrayList<Character> u = new ArrayList<Character>();
		
		
		solve(s,t,u,'a');
		
		StringBuilder sb = new StringBuilder();
		for(char c : u) {
			sb.append(c);
		}
		System.out.println(sb.toString());
		
		br.close();
		bw.close();
	}
	

	static void solve(ArrayList<Character> s,ArrayList<Character> t,ArrayList<Character> u, char search) {
		
//		System.out.println(search);
//		System.out.println(s.toString());
//		System.out.println(t.toString());
//		System.out.println(u.toString());
		
		

		if(s.size() == 0 && t.size() == 0) {
			return;
		} else if(s.size() == 0) {
			Collections.reverse(t);
			u.addAll(t);
		} else {
			
			while(t.size() > 0 && t.get(t.size()-1) <= search) {
				u.add(t.get(t.size()-1));
				t.remove(t.size()-1);
			}
			
			int lastIndexS = -1;
			for(int i = s.size()-1; i >= 0; --i) {
				//System.out.println(s.get(i).toString());
				if(s.get(i) == search) {
					lastIndexS = i;
					break;
				}
			}
			
			if(lastIndexS != -1) {
				for(int i = 0; i <= lastIndexS; ++i) {
					if(s.get(i) == search) {
						u.add(s.get(i));
					} else {
						t.add(s.get(i));
					}
				}
				s.subList(0,lastIndexS+1).clear();
			}
			solve(s,t,u,++search);

		}
	}
	
}

