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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Stack;
import java.util.StringTokenizer;

/*
 public class _697C {

 }

 */

public class _797C
{
	class ele
	{
		int num;
		int cnt;

		public ele(int num, int cnt)
		{
			super();
			this.num = num;
			this.cnt = cnt;
		}
	}

	public void solve() throws FileNotFoundException
	{
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		// actual solution

		String s = inputHelper.read();

		int n = s.length();

		char[] mina = new char[n];

		char min = Character.MAX_VALUE;
		for (int i = n - 1; i >= 0; i--)
		{
			mina[i] = min;
			min = (char) Math.min(min, s.charAt(i));
		}

		Stack<Character> stack = new Stack<Character>();

		StringBuilder ans = new StringBuilder();

		int i = -1;
		while (i < n - 1)
		{
			if (stack.isEmpty())
			{
				stack.add(s.charAt(++i));
			}

			while (i < n - 1 && stack.peek() > mina[i])
			{
				stack.add(s.charAt(++i));
			}

			while (!stack.isEmpty() && stack.peek() <= mina[i])
			{
				ans.append(stack.pop());
			}
		}

		while (!stack.isEmpty())
		{
			ans.append(stack.pop());
		}

		System.out.println(ans.toString());
		// end here
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		(new _797C()).solve();
	}

	class InputHelper
	{
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream)
		{
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					String line = bufferedReader.readLine();
					if (line == null)
					{
						return null;
					}
					tokenizer = new StringTokenizer(line);
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger()
		{
			return Integer.parseInt(read());
		}

		public Long readLong()
		{
			return Long.parseLong(read());
		}
	}
}