Problem: Given a string s, determine if it contains any palindrome of length exactly 100 as a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of s and is as long as possible.

Input

The only line of the input contains one string s of length n (1 ≤ n ≤ 5·104) containing only lowercase English letters.

Output

If s contains a palindrome of length exactly 100 as a subsequence, print any palindrome of length 100 which is a subsequence of s. If s doesn't contain any palindromes of length exactly 100, print a palindrome that is a subsequence of s and is as long as possible.

If there exists multiple answers, you are allowed to print any of them.

Examples

Input

bbbabcbbb


Output

bbbcbbb


Input

rquwmzexectvnbanemsmdufrg


Output

rumenanemur

Note

A subsequence of a string is a string that can be derived from it by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward or backward.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
mt19937 rng(steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long long mod = 1000000007;
long long madd(long long a, long long b) { return (a + b) % mod; }
long long msub(long long a, long long b) {
  return (((a - b) % mod) + mod) % mod;
}
long long mmul(long long a, long long b) {
  return ((a % mod) * (b % mod)) % mod;
}
long long mpow(long long base, long long exp) {
  long long res = 1;
  while (exp) {
    if (exp % 2 == 1) {
      res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}
long long minv(long long base) { return mpow(base, mod - 2); }
long long mdiv(long long a, long long b) { return mmul(a, minv(b)); }
long long gcd(long long x, long long y) {
  if (x == 0) return y;
  if (y == 0) return x;
  return gcd(y, x % y);
}
bool prime[1000006];
void sieve(int n) {
  for (long long i = 0; i < n + 1; i++) prime[i] = 1;
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  prime[1] = prime[0] = 0;
}
long long n, m, k, q, Q, T, l, r, x, y, z;
long long a[500005];
long long b[500005];
string second, t;
long long ans = 0;
int lps[3001][3001];
int par[3001][3001];
int cnt[29];
int get(int l, int r) {
  if (l < 0 || r >= n) return -1;
  if (lps[l][r] != -1) return lps[l][r];
  if (l == r) return lps[l][r] = 1;
  if (second[l] == second[r]) {
    if (l == r - 1)
      lps[l][r] = 2;
    else
      lps[l][r] = 2 + get(l + 1, r - 1);
    par[l][r] = 0;
  }
  int a = get(l + 1, r);
  int b = get(l, r - 1);
  if (lps[l][r] >= max(a, b))
    par[l][r] = 0;
  else if (a > b)
    par[l][r] = 1;
  else
    par[l][r] = 2;
  lps[l][r] = max(lps[l][r], max(a, b));
  return lps[l][r];
}
bool first = 0;
string pr(int l, int r) {
  if (l == r) {
    if (first) return "";
    return second.substr(l, 1);
  }
  if (par[l][r] == 0) {
    if (l == r - 1) return second.substr(l, 2);
    return second.substr(l, 1) + pr(l + 1, r - 1) + second.substr(r, 1);
  } else if (par[l][r] == 1) {
    return pr(l + 1, r);
  } else {
    return pr(l, r - 1);
  }
}
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  };
  cin >> second;
  n = second.length();
  memset(cnt, 0, sizeof(cnt));
  for (long long i = 0; i < n; i++) cnt[second[i] - 'a']++;
  for (long long i = 0; i < 26; i++)
    if (cnt[i] >= 100) {
      for (long long j = 0; j < 100; j++) cout << (char)(i + 'a');
      cout << endl;
      exit(0);
    }
  for (long long i = 0; i < n + 5; i++)
    for (long long j = 0; j < n + 5; j++) lps[i][j] = -1;
  for (long long i = 0; i < n; i++)
    for (long long j = i; j < n; j++) get(i, j);
  if (get(0, n - 1) >= 100) {
    for (long long i = 0; i < n; i++)
      for (long long j = i; j < n; j++)
        if (get(i, j) == 100 || get(i, j) == 101) {
          first = 1;
          cout << pr(i, j) << endl;
          exit(0);
        }
  }
  first = 0;
  cout << pr(0, n - 1) << endl;
}