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 Q3 {
	
	static InputReader in=new InputReader(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	static int T=1,N,M;
	static int A[];
 	static int dp[][];
	static ArrayList<Integer> graph[];
	public static void main(String args[])
	{
		int i,j;
		//T=in.readInt();
		while(T-->0)
		{
			String s=in.readString();
			int a[]=new int[26];
			for(i=0;i<s.length();i++)
			{
				a[(int)(s.charAt(i)-'a')]=i;
			}
			Stack<Integer> st=new Stack<Integer>();
			j=0;
			char u[]=new char[s.length()];
			int idx=0;
			for(i=0;i<26;i++)
			{
				
				while(!st.isEmpty()&&st.peek()<=i)
				{
					u[idx++]=(char)(st.pop()+97);
				}
				while(j<s.length()&&j<=a[i])
				{
					char ch1=s.charAt(j);
					if(ch1!=(char)(i+97))
					st.push((int)(ch1-'a'));
					else
					u[idx++]=(char)(i+97);
					j++;
				}
			}
			while(!st.isEmpty())
			{
				u[idx++]=(char)(st.pop()+97);
			}
			for(i=0;i<s.length();i++)
				out.print(u[i]);
		//	out.println(idx);
		}
		out.flush();
		out.close();
	}
	public static void printI0(int a[],int n)
	{
		for(int i=0;i<n;i++)
		{
			out.println(a[i]);
		}
	}
	public static void printI1(int a[],int n)
	{
		for(int i=1;i<=n;i++)
		{
			out.println(a[i]);
		}
	}	
	public static void printL0(long a[],int n)
	{
		for(int i=0;i<n;i++)
		{
			out.println(a[i]);
		}
	}
	public static void printL1(long a[],int n)
	{
		for(int i=1;i<=n;i++)
		{
			out.println(a[i]);
		}
	}
	public static void initializeGraph(int n)
	{
		graph=new ArrayList[n+1];
		for(int i=0;i<=n;i++)
			graph[i]=new ArrayList<Integer>();
	}
}
class Pair{
	int x,y;
	public Pair(int x,int y)
	{
		this.x=x;
		this.y=y;
	}
}
class InputReader{
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream){this.stream = stream;}
	public int read(){
		if (numChars==-1) throw new InputMismatchException();
		if (curChar >= numChars){
			curChar = 0;
			try {numChars = stream.read(buf);}
			catch (IOException e){throw new InputMismatchException();}
			if(numChars <= 0) return -1;
		}
		return buf[curChar++];
	}

	public int readInt(){
		int c = read();
		while(isSpaceChar(c)) c = read();
		int sgn = 1;
		if (c == '-') {sgn = -1;c = read();}
		int res = 0;
		do {
			if(c<'0'||c>'9') throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		}
		while (!isSpaceChar(c)); return res * sgn;
	}
	public void inputI0(int a[],int n)
	{
		for(int i=0;i<n;i++)
			a[i]=readInt();
	}
	public void inputI1(int a[],int n)
	{
		for(int i=1;i<=n;i++)
			a[i]=readInt();
	}
	public long readLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
      }
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
      }
		while (!isSpaceChar(c));
          return res * sgn;
  }
	public void inputL0(long a[],int n)
	{
		for(int i=0;i<n;i++)
			a[i]=readLong();
	}
	public void inputL1(long a[],int n)
	{
		for(int i=1;i<=n;i++)
			a[i]=readLong();
	}
	public double readDouble() {
      int c = read();
      while (isSpaceChar(c))
          c = read();
      int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
      }
		double res = 0;
		while (!isSpaceChar(c) && c != '.') {
			if (c == 'e' || c == 'E')
				return res * Math.pow(10, readInt());
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
      }
		if (c == '.') {
			c = read();
			double m = 1;
			while (!isSpaceChar(c)) {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				m /= 10;
				res += (c - '0') * m;
				c = read();
          }
      }
		return res * sgn;
  }

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}