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_base::sync_with_stdio(false);
  cin.tie(NULL);
  list<char> t, u;
  int freq[26];
  string inp;
  for (int i = 0; i < 26; i++) freq[i] = 0;
  cin >> inp;
  for (int i = 0; i < inp.length(); i++) {
    freq[inp[i] - 'a']++;
  }
  int it = 0;
  while (it < inp.length()) {
    int f = 0;
    char MinCh = '$';
    for (int i = 0; i < 26 && !f; i++) {
      if (freq[i]) {
        MinCh = (char)'a' + i;
        f = 1;
      }
    }
    if (MinCh == '$') {
      break;
    }
    f = 0;
    while (!f && !t.empty()) {
      if (t.back() <= MinCh) {
        u.push_back(t.back());
        t.pop_back();
      } else {
        f = 1;
      }
    }
    while (inp[it] != MinCh) {
      t.push_back(inp[it]);
      freq[inp[it] - 'a']--;
      it++;
    }
    u.push_back(inp[it]);
    freq[inp[it] - 'a']--;
    it++;
  }
  while (!t.empty()) {
    u.push_back(t.back());
    t.pop_back();
  }
  for (auto mx = u.begin(); mx != u.end(); mx++) {
    cout << *mx;
  }
  cout << endl;
}
