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
public class SolveC {
    public static void main(String[] args) throws java.io.IOException {
		try (java.io.BufferedReader in = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
			java.io.PrintWriter out = new java.io.PrintWriter(new java.io.BufferedOutputStream(System.out))) {
			String s = in.readLine();	
			int[] rem = new int[26];
			char[] ans = new char[s.length()];
			int k = 0;
			java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
			for (int i = 0; i < s.length(); i++)
				rem[s.charAt(i) - 'a']++;
			int pos = -1;
			for (char curr = 'a'; curr <= 'z'; curr++) {
				while (!stack.isEmpty() && stack.peek() <= curr) {
					ans[k++] = stack.pop();
				}
				while (rem[curr - 'a'] != 0) {
					if (s.charAt(++pos) == curr) { 
						ans[k++] = curr;
					} else {
						stack.push(s.charAt(pos));
					}
					rem[s.charAt(pos) - 'a']--;
				}
			}
			while (!stack.isEmpty()) {
				ans[k++] = stack.pop();
			}
			out.println(new String(ans));
		}
	}
}
