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;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<long long int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long int ceil(long long int a, long long int b) { return (a + b - 1) / b; }
long long int digit(long long int a) { return (long long int)log10(a); }
long long int e_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
long long int m_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
bool check_overflow(long long int a, long long int b, long long int limit) {
  if (b == 0) return false;
  return a > limit / b;
}
void Worshall_Floyd(VVl& g) {
  for (long long int k = (0), k_end_ = (((long long int)(g).size()));
       k < k_end_; ++k)
    for (long long int i = (0), i_end_ = (((long long int)(g).size()));
         i < i_end_; ++i)
      for (long long int j = (0), j_end_ = (((long long int)(g).size()));
           j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const long long int MOD1000000007 = 1000000007, MOD998244353 = 998244353,
                    INF = 5e18;
long long int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1},
              dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  long long int from, to;
  long long int cost;
  Edge() {}
  Edge(long long int u, long long int v, long long int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  long long int to;
  long long int cost;
  WeightedEdge(long long int v, long long int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
long long int N;
int main() {
  string s;
  cin >> s;
  VVl pos(26);
  for (long long int i = (0), i_end_ = (((long long int)(s).size()));
       i < i_end_; ++i) {
    pos[s[i] - 'a'].push_back(i);
  }
  stack<char> st;
  string ans = "";
  long long int idx = 0;
  for (long long int i = (0), i_end_ = (26); i < i_end_; ++i) {
    while (!st.empty() && (st.top() - 'a') <= i) {
      ans += st.top();
      st.pop();
    }
    for (long long int j = (0), j_end_ = (((long long int)(pos[i]).size()));
         j < j_end_; ++j) {
      if (pos[i][j] < idx) continue;
      while (idx < pos[i][j]) {
        st.push(s[idx]);
        idx++;
      }
      ans += s[idx];
      idx++;
    }
  }
  while (!st.empty()) {
    ans += st.top();
    st.pop();
  }
  cout << ans << '\n';
}
