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;
long long binpow(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    y = y >> 1;
    x = (x * x);
  }
  return res;
}
long long binpowmod(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long mod_inverse(long long n, long long p) {
  return binpowmod(n, p - 2, p);
}
unsigned long long gcd(unsigned long long x, unsigned long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
bool comp(int x, int y) { return x >= y; }
bool comp_pairs_by_s(pair<long long, long long> &x,
                     pair<long long, long long> &y) {
  return x.second < y.second;
}
bool isPowerOfTwo(long long x) { return x && (!(x & (x - 1))); }
class cmp {
 public:
  bool operator()(pair<int, int> A, pair<int, int> B) {
    if (abs(A.first - A.second) == abs(B.first - B.second))
      return A.first > B.first;
    return abs(A.first - A.second) < abs(B.first - B.second);
  }
};
unordered_set<int> s1;
unordered_set<int> s2;
void dfs(int node, map<int, vector<int> > m, vector<int> g[], vector<int> vis) {
  vis[node] = 1;
  s1.insert(node);
  for (int it : m[node]) s2.insert(it);
  for (int to : g[node]) {
    if (!vis[to]) dfs(to, m, g, vis);
  }
}
char findsmallest(int arr[]) {
  for (int i = 0; i < 26; i++)
    if (arr[i] > 0) return 'a' + i;
  return 'a' + 27;
}
void solve() {
  string s, u = "";
  cin >> s;
  int n = s.length();
  int leftcnt[26] = {0};
  vector<char> st;
  for (int i = 0; i < n; i++) leftcnt[s[i] - 'a']++;
  for (int i = 0; i < n; i++) {
    char c = findsmallest(leftcnt);
    if (st.empty()) {
      if (c == s[i]) {
        leftcnt[c - 'a']--;
        u += c;
      } else {
        st.push_back(s[i]);
        leftcnt[s[i] - 'a']--;
      }
    } else if (c < st[st.size() - 1] && !st.empty()) {
      if (c == s[i]) {
        leftcnt[c - 'a']--;
        u += c;
      } else {
        st.push_back(s[i]);
        leftcnt[s[i] - 'a']--;
      }
    } else if (!st.empty() && c >= st[st.size() - 1]) {
      while (c >= st[st.size() - 1] && !st.empty()) {
        char ch = st[st.size() - 1];
        st.pop_back();
        u += ch;
      }
      if (c == s[i]) {
        leftcnt[c - 'a']--;
        u += c;
      } else {
        st.push_back(s[i]);
        leftcnt[s[i] - 'a']--;
      }
    }
  }
  while (!st.empty()) {
    u += st[st.size() - 1];
    st.pop_back();
  }
  cout << u;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}
