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;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const long long mod = 1000 * 1000 * 100;
const long long inf = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 7;
const long long mod2 = 998244353;
const long long N = 1000 * 1000 + 100;
const long double pi = 3.141592653589793;
long long power(long long x, long long y, long long p = LLONG_MAX) {
  long long res = 1;
  x %= p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
string lcs(string &X, string &Y) {
  long long m = X.length(), n = Y.length();
  long long L[m + 1][n + 1];
  for (long long i = 0; i <= m; i++) {
    for (long long j = 0; j <= n; j++) {
      if (i == 0 || j == 0)
        L[i][j] = 0;
      else if (X[i - 1] == Y[j - 1])
        L[i][j] = L[i - 1][j - 1] + 1;
      else
        L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
  }
  long long index = L[m][n];
  string lcs(index, 'a');
  long long i = m, j = n;
  while (i > 0 && j > 0) {
    if (X[i - 1] == Y[j - 1]) {
      lcs[index - 1] = X[i - 1];
      i--;
      j--;
      index--;
    } else if (L[i - 1][j] > L[i][j - 1])
      i--;
    else
      j--;
  }
  return lcs;
}
string lps(string &str) {
  string rev = str;
  reverse(rev.begin(), rev.end());
  return lcs(str, rev);
}
void solve() {
  string s;
  cin >> s;
  long long f[26] = {0};
  for (long long i = 0; i < s.length(); i++) f[s[i] - 'a']++;
  long long u = 0, pos;
  for (long long i = 0; i < 26; i++) {
    if (u < f[i]) {
      u = f[i];
      pos = i;
    }
  }
  if (u >= 100) {
    long long u = 100;
    while (u--) cout << (char)('a' + pos);
  } else {
    string y = lps(s);
    if (y.length() < 100) {
      cout << y;
    } else {
      string x;
      for (long long i = 0; i < 50; i++) {
        x += y[i];
      }
      cout << x;
      reverse(x.begin(), x.end());
      cout << x;
      cout << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}