#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
long long int poww(long long int x, long long int n) {
  long long int res = 1;
  while (n > 0) {
    if (n % 2) res *= x;
    n = n >> 1;
    x *= x;
  }
  return res;
}
void solve() {
  string s;
  cin >> s;
  stack<char> st;
  long long int ptr = 0;
  string ans = "";
  long long int n = s.size();
  vector<char> vps(n, 'z');
  vps[n - 1] = s[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    if (s[i] <= vps[i + 1])
      vps[i] = s[i];
    else
      vps[i] = vps[i + 1];
  }
  for (int i = 0; i < n; i++) {
    st.push(s[i]);
    while (!st.empty() and st.top() <= vps[i + 1]) ans += st.top(), st.pop();
  }
  while (!st.empty()) ans += st.top(), st.pop();
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
  ;
  { solve(); }
}
