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;
vector<vector<long long> > v;
vector<bool> th(1010), ch(1010);
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
void swap(char a, char b) {
  char t;
  t = a;
  a = b;
  b = t;
}
long long fact(long long n) {
  if (n <= 1)
    return 1;
  else
    return n * fact(n - 1);
}
long long comb(long long n, long long k) {
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long GCD(long long a, long long b) {
  if (b == 1)
    return 1;
  else
    return GCD(b, a % b);
}
long long dig(long long n) {
  long long c = 0;
  while (n > 0) {
    long long x = n % 10;
    if (x != 0) c++;
    n = n / 10;
  }
  return c;
}
bool DFS(long long n) {
  bool ch[1010];
  stack<long long> s;
  long long ans = 0;
  ch[n] = true;
  s.push(n);
  if (th[n] == true) ans++;
  while (s.size() > 0) {
    long long x = s.top();
    s.pop();
    cout << "X";
    for (long long i = 0; i < v[x].size(); i++) {
      if (ch[v[x][i]] == false) {
        s.push(v[x][i]);
        ch[v[x][i]] = true;
        if (th[v[x][i]] == true) ans++;
        if (ans >= 2) {
          return false;
        }
      }
    }
  }
  return true;
}
queue<int> q;
void BFS(long long n) {
  long long i, le[n + 1];
  q.push(n);
  le[n] = 0;
  ch[n] = true;
  while (q.size() > 0) {
    long long x = q.front();
    q.pop();
    for (i = 0; i < v[x].size(); i++) {
      if (ch[v[x][i]] == false) {
        q.push(v[x][i]);
        ch[v[x][i]] = true;
        le[v[x][i]] = le[x] + 1;
      }
    }
  }
}
long long count(long long n) {
  long long c = 1, k = n;
  while (k > 0) {
    long long x = k % 10;
    if (x != 0) c = c * x;
    k = k / 10;
  }
  return c;
}
int main() {
  long long n, i;
  string s;
  char loc, loc2;
  cin >> s;
  n = s.length();
  map<char, long long> fr;
  for (i = 0; i < n; i++) fr[s[i]]++;
  stack<char> t;
  loc = 'a';
  for (i = 0; i < n; i++) {
    if (s[i] == loc) {
      cout << loc;
      fr[loc]--;
    } else {
      t.push(s[i]);
      fr[s[i]]--;
    }
    if (fr[loc] == 0) {
      while (fr[loc] == 0 && loc <= 'z') loc++;
      while (t.size() > 0) {
        if (t.top() <= loc) {
          cout << t.top();
          t.pop();
        } else
          break;
      }
    }
  }
}
