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;
char ss[100800];
int a[100800];
int minn[100800];
int main() {
  while (~scanf("%s", ss)) {
    int n = strlen(ss);
    memset(minn, 0, sizeof(minn));
    for (int i = 0; i < n; i++) a[i] = ss[i] - 'a' + 1;
    for (int i = n - 1; i >= 0; i--) {
      if (i == n - 1)
        minn[i] = a[i];
      else
        minn[i] = min(minn[i + 1], a[i]);
    }
    stack<char> s;
    for (int i = 0; i < n; i++) {
      if (s.size() == 0) {
        s.push(ss[i]);
      } else {
        while (!s.empty()) {
          int u = s.top() - 'a' + 1;
          if (u <= minn[i]) {
            printf("%c", s.top());
            s.pop();
          } else
            break;
        }
        s.push(ss[i]);
      }
    }
    while (!s.empty()) {
      printf("%c", s.top());
      s.pop();
    }
    printf("\n");
  }
}
