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 comment(linker, "/STACK:200000000")
const double EPS = 1E-9;
const int INF = 1000000000;
const long long INF64 = (long long)1E18;
const double PI = 3.1415926535897932384626433832795;
int z[2700][2700];
string s;
int c1, c2;
int rec(int l, int r) {
  if (l > r) return 0;
  if (l == r) return c1;
  if (z[l][r] != -1) return z[l][r];
  int res = max(rec(l + 1, r), rec(l, r - 1));
  if (s[l] == s[r]) res = max(rec(l + 1, r - 1) + 2, res);
  res = min(res, c2);
  return z[l][r] = res;
}
string lf, rg;
void recwrite(int l, int r) {
  if (l > r) return;
  if (l == r) {
    lf += s[l];
    return;
  }
  int res = z[l][r];
  if (res == rec(l + 1, r)) return recwrite(l + 1, r);
  if (res == rec(l, r - 1)) return recwrite(l, r - 1);
  lf += s[l];
  rg += s[r];
  recwrite(l + 1, r - 1);
}
int main() {
  getline(cin, s);
  vector<int> cnt(26);
  for (int i = 0; i < (int)(s.size()); i++) cnt[s[i] - 'a']++;
  for (int i = 0; i < (int)(26); i++)
    if (cnt[i] >= 100) {
      for (int j = 0; j < (int)(100); j++) putchar('a' + i);
      return 0;
    }
  memset(z, -1, sizeof(z));
  c1 = 1;
  c2 = INF;
  int res = rec(0, (int)s.size() - 1);
  recwrite(0, (int)s.size() - 1);
  reverse(rg.begin(), rg.end());
  lf += rg;
  if ((int)lf.size() > 100) {
    if ((int)lf.size() % 2 == 1) lf.erase(lf.size() / 2, 1);
    if ((int)lf.size() > 100) {
      int d = ((int)lf.size() - 100) / 2;
      lf.erase(0, d);
      lf.erase(lf.size() - d);
    }
  }
  puts(lf.c_str());
  return 0;
}