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;
bool tr[100009];
map<char, int> lst;
int main() {
  string s, ans = "";
  cin >> s;
  s = " " + s;
  char mn = 'z';
  for (int i = 1; i < s.size(); i++) {
    lst[s[i]] = i;
    mn = min(mn, s[i]);
  }
  for (int i = 1; i < s.size(); i++) {
    if (s[i] == mn) {
      ans += s[i];
      tr[i] = 1;
      if (lst[mn] == i) {
        char u = 'Z';
        for (char f = 'z'; f > mn; f--) {
          if (lst[f] > 0 && lst[f] > i) u = f;
        }
        if (u == 'Z')
          break;
        else {
          mn = u;
          for (int j = i - 1; j > 0; j--) {
            if (tr[j] == 0) {
              if (s[j] <= mn) {
                ans += s[j];
                tr[j] = 1;
              } else
                break;
            }
          }
        }
      }
    }
  }
  for (int i = s.size() - 1; i > 0; i--) {
    if (tr[i] == 0) ans += s[i];
  }
  cout << ans;
  return 0;
}
