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>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
void itval(istream_iterator<string> it) {}
template <typename T, typename... Args>
void itval(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  itval(++it, args...);
}
const long long int MOD = 1e9 + 7;
template <typename T>
inline void print(T x) {
  cout << x << "\n";
}
template <typename T>
inline void printvec(T x) {
  for (auto a : x) cout << a << ' ';
  cout << '\n';
}
struct custom {
  bool operator()(const pair<int, pair<int, int> > &p1,
                  const pair<int, pair<int, int> > &p2) const {
    return p1.first < p2.first;
  }
};
long long int get_pow(long long int a, long long int b, long long int M = MOD) {
  long long int res = 1;
  while (b) {
    if (b & 1) res = (res * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}
const long long int N = 2600 + 5, inf = 2e18;
int lookup[N][N];
string longestPalindrome(string X, string Y, int m, int n) {
  if (m == 0 || n == 0) {
    return string("");
  }
  if (X[m - 1] == Y[n - 1]) {
    return longestPalindrome(X, Y, m - 1, n - 1) + X[m - 1];
  }
  if (lookup[m - 1][n] > lookup[m][n - 1]) {
    return longestPalindrome(X, Y, m - 1, n);
  }
  return longestPalindrome(X, Y, m, n - 1);
}
int LCSLength(string X, string Y, int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) {
        lookup[i][j] = lookup[i - 1][j - 1] + 1;
      } else {
        lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);
      }
    }
  }
  return lookup[n][n];
}
void solve() {
  string s;
  cin >> s;
  int n = s.length();
  if (n >= 2600) {
    vector<long long> v(26, 0);
    for (auto c : s) v[c - 'a']++;
    for (long long int i = (long long int)0; i < (long long int)(26); i++) {
      if (v[i] >= 100) {
        for (long long int z = (long long int)0; z < (long long int)(100); z++)
          cout << char('a' + i);
        return;
      }
    }
  }
  string r = s;
  reverse(r.begin(), r.end());
  LCSLength(s, r, n);
  string res = longestPalindrome(s, r, n, n);
  if (res.length() <= 100) {
    cout << res;
    return;
  }
  string p = "";
  for (long long int i = (long long int)0; i < (long long int)(50); i++)
    p.push_back(res[i]);
  cout << p;
  reverse(p.begin(), p.end());
  cout << p;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test = 1;
  clock_t z = clock();
  for (long long int tes = (long long int)0; tes < (long long int)(test);
       tes++) {
    solve();
  }
  fprintf(stderr, "Total Time:%.4f\n", (double)(clock() - z) / CLOCKS_PER_SEC),
      fflush(stderr);
  return 0;
}