#include <bits/stdc++.h>
using namespace std;
template <class T>
T max2(T a, T b) {
  return a < b ? b : a;
}
template <class T>
T min2(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T max3(T a, T b, T c) {
  return max2(max2(a, b), c);
}
template <class T>
T min3(T a, T b, T c) {
  return min2(min2(a, b), c);
}
template <class T>
T max4(T a, T b, T c, T d) {
  return max2(max2(a, b), max2(c, d));
}
template <class T>
T min4(T a, T b, T c, T d) {
  return min2(min2(a, b), max2(c, d));
}
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
long long int bit_count(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
long long int bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? 0 : 1;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  if (a < b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
  }
  if (b == 0) return a;
  long long int t;
  while (b) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
pair<int, int> operator+(const pair<int, int>& l, const pair<int, int>& r) {
  pair<int, int> ret;
  ret.first = l.first + r.first;
  ret.second = l.second + r.second;
  return ret;
}
struct cmp {
  bool operator()(int const& l, int const& r) { return l > r; }
} myobject;
int main() {
  string second;
  cin >> second;
  vector<int> v[26];
  for (int i = 0; i < second.size(); i++) v[second[i] - 'a'].push_back(i);
  int last = -1;
  for (int i = 25; i >= 0; i--) {
    if (v[i].size() == 0) continue;
    for (int j = 0; j <= v[i].size() - 1; j++) {
      if (v[i][j] > last) {
        last = v[i][j];
        cout << (char)(i + 'a');
      }
    }
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

You've got string s, consisting of only lowercase English letters. Find its lexicographically maximum subsequence.

We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) a subsequence of string s = s1s2... s|s|.

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. Characters in lines are compared like their ASCII codes.

Input

The single line contains a non-empty string s, consisting only of lowercase English letters. The string's length doesn't exceed 105.

Output

Print the lexicographically maximum subsequence of string s.

Examples

Input

ababba


Output

bbba


Input

abbcbccacbbcbaaba


Output

cccccbba

Note

Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).

The first sample: aBaBBA

The second sample: abbCbCCaCbbCBaaBA

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
T max2(T a, T b) {
  return a < b ? b : a;
}
template <class T>
T min2(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T max3(T a, T b, T c) {
  return max2(max2(a, b), c);
}
template <class T>
T min3(T a, T b, T c) {
  return min2(min2(a, b), c);
}
template <class T>
T max4(T a, T b, T c, T d) {
  return max2(max2(a, b), max2(c, d));
}
template <class T>
T min4(T a, T b, T c, T d) {
  return min2(min2(a, b), max2(c, d));
}
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
long long int bit_count(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
long long int bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? 0 : 1;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  if (a < b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
  }
  if (b == 0) return a;
  long long int t;
  while (b) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
pair<int, int> operator+(const pair<int, int>& l, const pair<int, int>& r) {
  pair<int, int> ret;
  ret.first = l.first + r.first;
  ret.second = l.second + r.second;
  return ret;
}
struct cmp {
  bool operator()(int const& l, int const& r) { return l > r; }
} myobject;
int main() {
  string second;
  cin >> second;
  vector<int> v[26];
  for (int i = 0; i < second.size(); i++) v[second[i] - 'a'].push_back(i);
  int last = -1;
  for (int i = 25; i >= 0; i--) {
    if (v[i].size() == 0) continue;
    for (int j = 0; j <= v[i].size() - 1; j++) {
      if (v[i][j] > last) {
        last = v[i][j];
        cout << (char)(i + 'a');
      }
    }
  }
  return 0;
}

```