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;
string S, T, U;
int N;
char is[101010];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> S;
  N = S.size();
  char c = 'z' + 1;
  for (i = N - 1; i >= 0; i--) {
    is[i] = c;
    c = min(c, S[i]);
  }
  for (i = 0; i < (N); i++) {
    while (T.size() && T.back() <= min(is[i], S[i])) {
      U.push_back(T.back());
      T.pop_back();
    }
    if (is[i] < S[i]) {
      T.push_back(S[i]);
    } else {
      while (T.size() && T.back() <= S[i]) {
        U.push_back(T.back());
        T.pop_back();
      }
      U.push_back(S[i]);
    }
  }
  while (T.size()) {
    U.push_back(T.back());
    T.pop_back();
  }
  cout << U << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
