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 siev[1000005];
inline void Scan_f(int &a) {
  char c = 0;
  while (c < 33) c = getc(stdin);
  a = 0;
  while (c > 33) {
    a = a * 10 + c - '0';
    c = getc(stdin);
  }
}
void sieve() {
  for (int i = 2; i <= 1e6; i++) {
    if (siev[i] == 0) {
      for (int j = i; j <= 1e6; j += i) siev[j] = i;
    }
  }
}
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  while (b != 0) {
    long long temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
int check(int cnt[], char ch) {
  long long hh = ch - 'a';
  for (int i = 0; i < hh; i++)
    if (cnt[i]) return 0;
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string str;
  cin >> str;
  vector<char> a, b;
  int cnt[26] = {0};
  for (long long i = 0; i < str.length(); i++) cnt[str[i] - 'a'] += 1;
  long long k = 0;
  long long n = str.length();
  while (b.size() != str.length() && k < n) {
    int g = a.size();
    if (g && check(cnt, a[g - 1])) {
      b.push_back(a[g - 1]);
      a.pop_back();
    } else if (check(cnt, str[k])) {
      cnt[str[k] - 'a'] -= 1;
      b.push_back(str[k++]);
    } else {
      cnt[str[k] - 'a'] -= 1;
      a.push_back(str[k++]);
    }
  }
  while (a.size()) {
    int m = a.size() - 1;
    b.push_back(a[m]);
    a.pop_back();
  }
  for (int i = 0; i < b.size(); i++) cout << b[i];
  return 0;
}
