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;
template <class T>
using vv = vector<vector<T>>;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &t) {
  os << "{";
  for (int(i) = 0; (i) < (t.size()); ++(i)) {
    os << t[i] << ",";
  }
  os << "}" << endl;
  return os;
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &t) {
  return os << "(" << t.first << "," << t.second << ")";
}
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
vector<string> s_p_l_i_t(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void e_r_r(vector<string>::iterator it) {}
template <typename T, typename... Args>
void e_r_r(vector<string>::iterator it, T a, Args... args) {
  if (*it == " 1" || *it == "1")
    cerr << endl;
  else
    cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << ", ";
  e_r_r(++it, args...);
}
const long long MOD = 1e9 + 7;
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(0);
  string s;
  cin >> s;
  int n = s.size();
  vector<int> last(200);
  for (int(i) = 0; (i) < (n); ++(i)) last[s[i]] = i;
  stack<char> st;
  string re;
  int ind = 0;
  for (int(c) = 'a'; (c) < ('z' + 1); ++(c)) {
    while (st.size() && st.top() <= c) re += st.top(), st.pop();
    for (int(i) = ind; (i) < (last[c] + 1); ++(i)) {
      if (s[i] == c) {
        re += c;
      } else {
        st.push(s[i]);
      }
    }
    MX(ind, last[c] + 1);
  }
  while (st.size()) re += st.top(), st.pop();
  cout << re << endl;
  return 0;
}
