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

public class EducationalRound19C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder t = new StringBuilder();
        StringBuilder u = new StringBuilder();
        PriorityQueue<Que> pq = new PriorityQueue<>();

        for(int i = 0; i < s.length(); i++){
            pq.add(new Que(s.charAt(i), i));
        }
        int ind = 0;
        while(!pq.isEmpty() || t.length() > 0){
            char nextT = 'z'+1;
            Que nextPQ = null;
            if(t.length() > 0){
                nextT = t.charAt(t.length()-1);
            }
            while(!pq.isEmpty()){
                nextPQ = pq.peek();
                if(nextPQ.pos < ind){
                    pq.poll();
                } else{
                    break;
                }
            }
            if(nextPQ != null && nextPQ.c< nextT){
                for(int i = ind; i < nextPQ.pos; i++){
                    t.append(s.charAt(i));
                }
                u.append(nextPQ.c);
                ind = nextPQ.pos+1;
                pq.poll();
            }
            else{
                u.append(nextT);
                t.deleteCharAt(t.length()-1);
            }
        }
        System.out.println(u.toString());
    }

    private static class Que implements Comparable<Que>{
        char c;
        int pos;

        Que(char c, int pos){
            this.c = c;
            this.pos = pos;
        }

        @Override
        public int compareTo(Que o) {
            if(this.c == o.c){
                return Integer.compare(this.pos, o.pos);
            }
            else{
                return Character.compare(this.c, o.c);
            }
        }
    }
}
