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 a[1111];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  string ans;
  deque<char> d;
  int n = s.length();
  for (long long i = (0); i < (1111); i++) a[i] = -1;
  for (long long i = (0); i < (n); i++) {
    a[s[i]] = i;
  }
  char c = 'a';
  int i = 0;
  while (c <= 'z') {
    while (!d.empty() && d.back() <= c) ans += d.back(), d.pop_back();
    for (long long o = (i); o < (a[c] + 1); o++) {
      if (s[o] == c)
        ans += c;
      else
        d.push_back(s[o]);
    }
    i = max(i, a[c] + 1);
    c++;
  }
  if (!d.empty())
    for (long long o = (int(d.size()) - 1); o >= (0); o--) ans += s[o];
  cout << ans;
  return 0;
}
