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 TestClass {

	static PrintWriter out = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception{
        
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		int n = s.length();
		int a[] = new int[n];
		a[n-1] = s.charAt(n-1);
		for(int i=n-2;i>=0;i--)
		{
			a[i] = Math.min(a[i+1], s.charAt(i));
		}
		StringBuilder t = new StringBuilder();
		StringBuilder u = new StringBuilder();
		for(int i=0;i<n;i++)
		{
			while(t.length()>0 && (t.charAt(t.length()-1)<=a[i]))
			{
				u.append(t.charAt(t.length()-1));
				t.deleteCharAt(t.length()-1);
			}

			if(a[i]==s.charAt(i))
			{
				u.append(s.charAt(i));
			}
			else
			{
				t.append(s.charAt(i));
			}
		}
		u.append(t.reverse());
		out.println(u);
		out.close();
    }
}

