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;
long long f[2601][2601], trace[2601][2601];
int main() {
  string a;
  int aa = 0, bb = 0, cc = 0, dd = 0, ee = 0, ff = 0, gg = 0, hh = 0, ii = 0,
      jj = 0, kk = 0, ll = 0, mm = 0, nn = 0, oo = 0, pp = 0, qq = 0, rr = 0,
      ss = 0, tt = 0, uu = 0, vv = 0, ww = 0, xx = 0, yy = 0, zz = 0;
  cin >> a;
  long long n = a.length();
  if (n >= 2600) {
    for (int i = 0; i < n; i++) {
      if (a[i] == 'a') {
        aa++;
      }
      if (a[i] == 'b') {
        bb++;
      }
      if (a[i] == 'c') {
        cc++;
      }
      if (a[i] == 'd') {
        dd++;
      }
      if (a[i] == 'e') {
        ee++;
      }
      if (a[i] == 'f') {
        ff++;
      }
      if (a[i] == 'g') {
        gg++;
      }
      if (a[i] == 'h') {
        hh++;
      }
      if (a[i] == 'i') {
        ii++;
      }
      if (a[i] == 'j') {
        jj++;
      }
      if (a[i] == 'k') {
        kk++;
      }
      if (a[i] == 'l') {
        ll++;
      }
      if (a[i] == 'm') {
        mm++;
      }
      if (a[i] == 'n') {
        nn++;
      }
      if (a[i] == 'p') {
        pp++;
      }
      if (a[i] == 'q') {
        qq++;
      }
      if (a[i] == 'r') {
        rr++;
      }
      if (a[i] == 's') {
        ss++;
      }
      if (a[i] == 't') {
        tt++;
      }
      if (a[i] == 'u') {
        uu++;
      }
      if (a[i] == 'v') {
        vv++;
      }
      if (a[i] == 'w') {
        ww++;
      }
      if (a[i] == 'x') {
        xx++;
      }
      if (a[i] == 'y') {
        yy++;
      }
      if (a[i] == 'z') {
        zz++;
      }
      if (aa == 100 || bb == 100 || cc == 100 || dd == 100 || ee == 100 ||
          ff == 100 || gg == 100 || hh == 100 || ii == 100 || jj == 100 ||
          kk == 100 || ll == 100 || mm == 100 || nn == 100 || oo == 100 ||
          pp == 100 || qq == 100 || rr == 100 || ss == 100 || tt == 100 ||
          uu == 100 || vv == 100 || ww == 100 || xx == 100 || yy == 100 ||
          zz == 100) {
        break;
      }
    }
    if (aa == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "a";
      }
    }
    if (bb == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "b";
      }
    }
    if (cc == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "c";
      }
    }
    if (dd == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "d";
      }
    }
    if (ee == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "e";
      }
    }
    if (ff == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "f";
      }
    }
    if (gg == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "g";
      }
    }
    if (hh == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "h";
      }
    }
    if (ii == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "i";
      }
    }
    if (jj == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "j";
      }
    }
    if (kk == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "k";
      }
    }
    if (ll == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "l";
      }
    }
    if (mm == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "m";
      }
    }
    if (nn == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "n";
      }
    }
    if (oo == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "o";
      }
    }
    if (pp == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "p";
      }
    }
    if (qq == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "q";
      }
    }
    if (rr == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "r";
      }
    }
    if (ss == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "s";
      }
    }
    if (tt == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "t";
      }
    }
    if (uu == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "u";
      }
    }
    if (vv == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "v";
      }
    }
    if (ww == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "w";
      }
    }
    if (xx == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "x";
      }
    }
    if (yy == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "y";
      }
    }
    if (zz == 100) {
      for (int i = 1; i <= 100; i++) {
        cout << "z";
      }
    }
  } else {
    for (int i = 0; i < n; i++) {
      f[i][i] = 1;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        trace[i][j] = 0;
      }
    }
    long long x = 0, y = n - 1;
    for (int j = 1; j < n; j++) {
      bool ok = false;
      for (int i = 0; i < n - 1; i++) {
        if (i + j > n) {
          continue;
        } else {
          if (a[i] == a[i + j]) {
            f[i][i + j] = f[i + 1][i + j - 1] + 2;
            trace[i][i + j] = 1;
          } else {
            f[i][i + j] = max(f[i][i + j - 1], f[i + 1][i + j]);
          }
        }
      }
    }
    if (f[0][n - 1] == 1) {
      cout << a[0];
      return 0;
    }
    int l = 0, r = n - 1;
    string s1, s2;
    int cl, cr;
    while (l <= r) {
      if (trace[l][r] == 1) {
        cl = l;
        cr = r;
        s1 += a[l];
        s2 += a[r];
        l++;
        r--;
      } else {
        if (f[l + 1][r] >= f[l][r - 1]) {
          l++;
        } else
          r--;
      }
      if (s1.length() >= 50 || s2.length() >= 50) break;
    }
    if (cl != cr - 1 && s1.length() < 50) s2 += a[cl + 1];
    reverse(s2.begin(), s2.end());
    cout << s1 << s2;
  }
}