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>
#pragma comment(linker, "/stack:16777216")
namespace Template {
using namespace std;
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
template <typename T>
void sci(T &t) {
  cin >> t;
}
template <typename T, typename... Ts>
void sci(T &t, Ts &...ts) {
  cin >> t;
  sci(ts...);
}
template <typename T>
inline T gcd(T a, T b) {
  T c;
  while (b) {
    c = b;
    b = a % b;
    a = c;
  }
  return a;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const pair<T, S> &v) {
  os << "(";
  os << v.first << "," << v.second << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  int sz = v.size();
  for (int i = 0; i < sz; ++i) {
    os << v[i];
    if (i != sz - 1) os << ",";
  }
  os << "]\n";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  T last = *v.rbegin();
  os << "[";
  for (auto it : v) {
    os << it;
    if (it != last) os << ",";
  }
  os << "]\n";
  return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &v) {
  for (auto it : v) {
    os << it.first << " : " << it.second << " , ";
  }
  return os;
}
long long powmod(long long a, long long b, long long mo) {
  long long res = 1;
  a %= mo;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mo;
    a = a * a % mo;
  }
  return res;
}
struct _runCode {
  clock_t time;
  int m;
  _runCode(int mode) {
    m = mode;
    if (mode == -1)
      freopen(
          "C:\\Users\\Praveen\\documents\\Visual Studio "
          "2017\\Projects\\comp\\in.txt",
          "w", stdout);
    if (mode >= 1)
      freopen(
          "C:\\Users\\Praveen\\documents\\Visual Studio "
          "2017\\Projects\\comp\\in.txt",
          "r", stdin);
    if (mode == 2)
      freopen(
          "C:\\Users\\Praveen\\documents\\Visual Studio "
          "2017\\Projects\\comp\\out.txt",
          "w", stdout);
    time = clock();
  }
  ~_runCode() {
    cerr << "\nTime: " << ((float)(clock() - time) / CLOCKS_PER_SEC) << '\n';
    if (m == -1 || m == 1) fcloseall();
  }
};
};  // namespace Template
using namespace Template;
vector<int> primes;
vector<int> p(100030, 0);
void generatePrime() {
  p[0] = p[1] = -1;
  for (int i = 2; i < p.size(); i++) {
    if (p[i] == 0) {
      primes.push_back(i);
      p[i] = i;
      for (int j = 2; j * i < p.size(); j++) p[i * j] = i;
    }
  }
}
void solveB() {
  int n;
  sci(n);
  ;
  vector<int> a(n);
  for (int i = 0; i < (int)n; ++i) cin >> a[i];
  int o, e;
  e = o = INT_MIN + 100000;
  for (int i = 0; i < (int)n; ++i) {
    if (int(abs(a[i])) % 2) {
      o = ((o) > (((e + a[i]) > (a[i]) ? (e + a[i]) : (a[i])))
               ? (o)
               : (((e + a[i]) > (a[i]) ? (e + a[i]) : (a[i]))));
      e = ((e) > (o + a[i]) ? (e) : (o + a[i]));
    } else {
      o = ((o) > (o + a[i]) ? (o) : (o + a[i]));
      e = ((e) > (((e + a[i]) > (a[i]) ? (e + a[i]) : (a[i])))
               ? (e)
               : (((e + a[i]) > (a[i]) ? (e + a[i]) : (a[i]))));
    }
  }
  cout << o;
}
void solve() {
  string s;
  sci(s);
  vector<int> cnt(26, 0);
  stack<char> S;
  for (int i = 0; i < (int)((int)(s.size())); ++i) {
    cnt[s[i] - 'a']++;
    S.push(s[((int)(s.size())) - i - 1]);
  }
  stack<char> t;
  string u = "";
  while (!S.empty() || !t.empty()) {
    if (!t.empty()) {
      char c = t.top();
      int k = c - 'a';
      bool no_ele = true;
      for (int i = 0; i < (int)k; ++i) {
        if (cnt[i] > 0) no_ele = false;
      }
      if (no_ele == false) {
        t.push(S.top());
        cnt[S.top() - 'a']--;
        ;
        S.pop();
      } else {
        u += t.top();
        ;
        t.pop();
      }
    } else {
      t.push(S.top());
      cnt[S.top() - 'a']--;
      ;
      S.pop();
    }
  }
  cout << u;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  ;
  solve();
  return 0;
}
