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 = 100000 + 10;
char num[maxn << 2];
char str[maxn];
stack<char> st;
void build(int l, int r, int rt) {
  if (l == r) {
    num[rt] = str[l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  num[rt] = min(num[rt << 1], num[rt << 1 | 1]);
}
char query(int l, int r, int rt, int a, int b) {
  if (a <= l && b >= r) {
    return num[rt];
  }
  int mid = (l + r) >> 1;
  if (mid >= b) {
    return query(l, mid, rt << 1, a, b);
  } else if (mid < a) {
    return query(mid + 1, r, rt << 1 | 1, a, b);
  } else {
    return min(query(l, mid, rt << 1, a, mid),
               query(mid + 1, r, rt << 1 | 1, mid + 1, b));
  }
}
int main() {
  while (~scanf("%s", str)) {
    while (!st.empty()) st.pop();
    int cnt = 0, len = strlen(str);
    build(1, len, 1);
    while (cnt < len) {
      if (cnt != len - 1 && str[cnt] <= query(1, len, 1, cnt + 2, len)) {
        printf("%c", str[cnt]);
        while (!st.empty() && st.top() <= query(1, len, 1, cnt + 2, len)) {
          printf("%c", st.top());
          st.pop();
        }
      } else {
        st.push(str[cnt]);
      }
      cnt++;
    }
    while (!st.empty()) {
      printf("%c", st.top());
      st.pop();
    }
    printf("\n");
  }
  return 0;
}
