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;
void solve_this() {
  long long int i, n, j, k, chk, l;
  string str;
  cin >> str;
  n = str.size();
  stack<char> st;
  l = 0;
  for (i = 'a'; i <= 'z'; i++) {
    while (!st.empty() && st.top() <= i) {
      cout << st.top();
      st.pop();
    }
    chk = 0;
    for (j = n - 1; j >= l; j--) {
      if (str[j] == i) {
        chk = 1;
        break;
      }
    }
    if (chk == 1) {
      for (k = l; k <= j; k++) {
        if (str[k] != i)
          st.push(str[k]);
        else
          cout << (char)i;
      }
      l = j + 1;
    }
  }
  while (!st.empty()) {
    cout << st.top();
    st.pop();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve_this();
  return 0;
}
