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;
const long double pi = 2 * acos(0.0);
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class TT>
bool pal(T a, TT n) {
  int k = 0;
  for (int i = 0; i <= n / 2; i++) {
    if (a[i] != a[n - i - 1]) {
      k = 1;
      break;
    }
  }
  return k ? 0 : 1;
}
int dp[222222];
int main() {
  string s;
  cin >> s;
  int n = s.size();
  int mn = 1e9;
  for (int i = n - 1; i >= 0; i--) mn = min(mn, (int)s[i]), dp[i] = mn;
  string t = "", res = "";
  for (int i = 0; i < n; i++) {
    while (t.size() && t.back() <= dp[i]) {
      res += t.back();
      t.erase(t.size() - 1, 1);
    }
    t += s[i];
    if ((int)s[i] <= dp[i]) {
      while (t.size() && t.back() <= dp[i]) {
        res += t.back();
        t.erase(t.size() - 1, 1);
      }
    }
  }
  reverse(t.begin(), t.end());
  res += t;
  cout << res;
  getchar();
  getchar();
  return 0;
}
