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;
const int maxn = 1e5 + 5;
char s[maxn], u[maxn];
stack<char> t;
int main() {
  char pp;
  scanf("%s", s);
  int len = strlen(s);
  int p = 0, u1 = 0;
  for (int i = 0; i < 26; ++i) {
    for (int j = p; j < len; ++j) {
      if (s[j] == 'a' + i) {
        while (!t.empty() && t.top() <= s[j]) u[u1++] = t.top(), t.pop();
        while (p < j && p < len) t.push(s[p++]);
        ++p;
        u[u1++] = s[j];
      }
    }
  }
  while (!t.empty()) {
    pp = t.top();
    t.pop();
    u[u1++] = pp;
  }
  printf("%s\n", u);
  return 0;
}
