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
#include <bits/stdc++.h>
using namespace std;
int dx[] = {+1, -1, 0, 0};
int dy[] = {0, 0, +1, -1};
int dx2[] = {+1, -1, 0, 0, +1, +1, -1, -1};
int dy2[] = {0, 0, +1, -1, +1, -1, -1, +1};
inline long long squ(long long x) { return (x * x); }
inline long long power(long long bs, long long k) {
  long long x = 1LL, y = bs;
  if (k == 0) return 1LL;
  while (k > 0) {
    if (k % 2) x *= y;
    y *= y;
    k /= 2;
  }
  return x;
}
int main() {
  cout.unsetf(ios::floatfield);
  cout.precision(6);
  cout.setf(ios::fixed, ios::floatfield);
  ;
  char s[100100], t[100100], cp[100100], mn[100100];
  int l1 = 0, l2 = 0, l3 = 0, i, j, k;
  scanf("%s", s);
  l1 = strlen(s);
  mn[l1] = 'z' + 1;
  for (i = l1 - 1; i >= 0; i--) mn[i] = min(mn[i + 1], s[i]);
  for (i = 0; i < l1; i++) {
    cp[l2++] = s[i];
    while (l2 && cp[l2 - 1] <= mn[i + 1]) {
      t[l3++] = cp[--l2];
    }
  }
  printf("%s", t);
  return 0;
}
