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;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  string a, temp, f = "";
  int ary2[1000] = {};
  stack<char> st;
  priority_queue<pair<char, int>, vector<pair<char, int>>,
                 greater<pair<char, int>>>
      pq;
  cin >> a;
  for (char i : a) ary2[int(i)]++;
  for (int i = 0; i < 1000; i++)
    if (ary2[i] != 0) pq.push({char(i), ary2[i]});
  memset(ary2, 0, sizeof(ary2));
  for (int i = 0; i < a.length(); i++) {
    ary2[int(a[i])]++;
    if (a[i] != pq.top().first)
      st.push(a[i]);
    else {
      f += pq.top().first;
      while (!pq.empty() && ary2[int(pq.top().first)] == pq.top().second) {
        pq.pop();
      }
      while (st.size() != 0 && pq.size() != 0 && st.top() <= pq.top().first)
        f += st.top(), st.pop();
    }
  }
  while (st.size() != 0) f += st.top(), st.pop();
  cout << f;
  return 0;
}
