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.Scanner;
import java.util.Stack;

public class c797Stack {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scn = new Scanner(System.in);
		String m = scn.nextLine();

		int n = m.length();

		char[] s = m.toCharArray();
		char[] mintill = new char[n];
		mintill[n - 1] = s[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			mintill[i] = (char) (Math.min(mintill[i + 1], s[i]));
		}

		Stack<Character> u = new Stack<>();
		Stack<Character> t = new Stack<>();

		for (int i = 0; i < n; i++) {
			while (!t.isEmpty() && t.peek() <= mintill[i]) {
				u.push(t.pop());
			}

			if (s[i] == mintill[i]) {
				u.push(s[i]);
			} else {
				t.push(s[i]);
			}
		}

		while (!t.isEmpty()) {
			u.push(t.pop());
		}

		for (int i = n - 1; i >= 0; i--) {
			s[i] = u.pop();

		}
		for (int i = 0; i < n; i++) {
			System.out.print(s[i]);
		}

	}

}
