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;
int strlen(char A[]) {
  int i = 0;
  while (A[i] != '\0' && A[i] != '\n') i++;
  return i;
}
void done(char A[], char B[], int C[]) {
  int n = strlen(A);
  B[n - 1] = A[n - 1];
  C[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; i--) {
    if (A[i] <= B[i + 1]) {
      B[i] = A[i];
      C[i] = i;
    } else {
      B[i] = B[i + 1];
      C[i] = C[i + 1];
    }
  }
}
int main() {
  char S[100001];
  scanf("%s", S);
  stack<char> T;
  list<char> U;
  int n = strlen(S);
  char B[n];
  int C[n];
  done(S, B, C);
  char m;
  int index;
  int i = 0;
  while (i < n) {
    if (!T.empty()) {
      m = T.top();
      index = -1;
    } else {
      m = S[i];
      index = i;
    }
    if (B[i] < m) {
      if (B[i] < m) {
        m = B[i];
        index = C[i];
      }
    }
    if (index == -1) {
      U.push_back(T.top());
      T.pop();
    } else {
      for (int j = i; j < index; j++) {
        T.push(S[j]);
      }
      U.push_back(S[index]);
      i = index + 1;
    }
  }
  while (!T.empty()) {
    U.push_back(T.top());
    T.pop();
  }
  list<char>::iterator itr;
  for (itr = U.begin(); itr != U.end(); itr++) {
    printf("%c", *itr);
  }
  return 0;
}
