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;

public class C {
	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			final String text = s.next();
			final int n = text.length();
			final int[] dp = new int[n];
			dp[n - 1] = text.charAt(text.length() - 1);
			for (int i = n - 2; i >= 0; --i) {
				dp[i] = Math.min(text.charAt(i), dp[i + 1]);
			}
			StringBuilder u = new StringBuilder();
			StringBuilder t = new StringBuilder();
			for (int i = 0; i < n; ++i) {
				while (t.length() > 0 && t.charAt(t.length() - 1) <= dp[i]) {
					u.append(t.charAt(t.length() - 1));
					t.deleteCharAt(t.length() - 1);
				}
				if (text.charAt(i) == dp[i]) {
					u.append(text.charAt(i));
				} else {
					t.append(text.charAt(i));
				}
			}
			u.append(t.reverse());
			System.out.println(u);
		}
	}
}
