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;
signed main() {
  ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
  string s;
  cin >> s;
  long long int len = s.length();
  string s1 = s;
  sort(s1.begin(), s1.end());
  stack<char> st;
  char dp[len + 1];
  dp[len] = 'z' + 3;
  for (long long int i = len - 1; i >= 0; i--) {
    dp[i] = min(dp[i + 1], s[i]);
  }
  string ans = "";
  long long int i = 0, index = 0;
  while (i != len) {
    if (s[i] == s1[index]) {
      ans += (s[i]);
      char temp = dp[i + 1];
      while (!st.empty() && st.top() <= temp) {
        char x = st.top();
        ans += (x);
        st.pop();
      }
      index++;
      while (s1[index] < dp[i + 1] && index < len) index++;
    } else
      st.push(s[i]);
    i++;
  }
  while (!st.empty()) {
    char x = st.top();
    ans += x;
    st.pop();
  }
  cout << ans;
  return 0;
}
