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.*;
import java.io.*;

public class Codechef
{
	public static void main (String[] args) throws Exception
	{
        // Reader sc = new Reader();
        // BufferOutput bufferOutput = new BufferOutput();
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        Stack<Character> t = new Stack<Character>();
        int a[] = new int[26];
        for (int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            a[c - 97]++;
        }
        int j = 0;
        for (int i = 0; i < 26; i++)
        {
            if (a[i] > 0)
            {
                while (!t.isEmpty() && t.peek() <= 97 + i)
                    System.out.print (t.pop());
                    
                for (; j < s.length(); j++)
                {
                    char c = s.charAt(j);
                    t.push(c);
                    a[c - 97] --;
                    if (c == 97 + i)
                    {
                        System.out.print (t.pop());
                        j++;
                        i--;
                        break;
                    }
                }
            }
            
        }
        while (!t.isEmpty())
            System.out.print (t.pop());
	}
}