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 Check(int N, int pos) { return (bool)(N & (1 << pos)); }
int Set(int N, int pos) { return N = N | (1 << pos); }
int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};
int hr[] = {-2, -2, -1, +1, +2, +2, -1, +1};
int hc[] = {+1, -1, +2, +2, -1, +1, -2, -2};
int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
const int MAXN = (int)1e5 + 9;
int main() {
  int i, j, k, l, m, n, p, q, x, y, v, r, tc;
  string s;
  cin >> s;
  l = s.size();
  int ara[30];
  memset(ara, -1, sizeof(ara));
  for (i = 0; i < l; i++) {
    ara[s[i] - 'a'] = i;
  }
  stack<char> t;
  string u = "";
  for (i = 0; i < l; i++) {
    t.push(s[i]);
    while (t.size() > 0) {
      char c = t.top();
      k = c - 'a';
      bool flag = false;
      for (j = 0; j < k; j++) {
        if (ara[j] > i) {
          flag = true;
          break;
        }
      }
      if (!flag) {
        t.pop();
        u += c;
      } else
        break;
    }
  }
  while (t.size() > 0) {
    u += t.top();
    t.pop();
  }
  cout << u << endl;
  return 0;
}
