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.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;


 public class Main{
     
     
     
     static class Pair{
         char val;
         int pos;
         public Pair(char val, int pos){
             this.val=val;
             this.pos=pos;
         }
     }
     
     public static void main(String[] args) throws IOException {
         //String IN = "C:\\Users\\ugochukwu.okeke\\Desktop\\in.file";
         //String OUT = "C:\\Users\\ugochukwu.okeke\\Desktop\\out.file";
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
         String S = br.readLine();
         
         char[] P = S.toCharArray();
         int n = P.length;
         int[] dp = new int[n];
         dp[n-1]=n-1;
         for(int i=n-2;i>=0;i--) {
             if(P[i] <= P[dp[i+1]]) dp[i] = i;
             else dp[i]=dp[i+1];
         }
         StringBuilder sb = new StringBuilder();
         Stack<Integer> D = new Stack<>();
         for(int i=0;i<n;i++) {
             if(D.isEmpty() || P[dp[i]] < P[D.peek()]) {
                 
                 D.push(i);
             }else {
                 
                 i-=1;
                 sb.append(P[D.pop()]);
             }
         }
         while(D.isEmpty()==false) sb.append(P[D.pop()]);
         bw.append(sb.toString()+"\n");
         bw.close();
     }
    //aabbbcbcc
 }