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;
const int N = 100100;
int c[30], d[2700][2700];
char s[N];
int main() {
  scanf("%s", s);
  int n = strlen(s);
  memset(c, 0, sizeof c);
  for (int i = 0; i < n; i++) {
    c[s[i] - 'a']++;
  }
  for (int i = 0; i < 26; i++) {
    if (c[i] >= 100) {
      for (int j = 0; j < 100; j++) {
        char ch = (char)('a' + i);
        printf("%c", ch);
      }
      puts("");
      exit(0);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      d[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    d[i][i] = 1;
    for (int j = i + 1; j < n; j++) {
      d[i][j] = ((s[i] == s[j]) ? 2 : 0);
    }
  }
  for (int l = 0; l <= n; l++) {
    for (int i = 0; i < n; i++) {
      int j = i + l;
      if (j >= n) {
        break;
      }
      if (i + 1 <= j) {
        d[i][j] = max(d[i][j], d[i + 1][j]);
      }
      if (i <= j - 1) {
        d[i][j] = max(d[i][j], d[i][j - 1]);
      }
      if (i + 1 <= j - 1 && s[i] == s[j]) {
        d[i][j] = max(d[i][j], d[i + 1][j - 1] + 2);
      }
    }
  }
  int i = 0;
  int j = n - 1;
  string x = "";
  string y = "";
  while (i <= j) {
    if (i + 1 <= j && d[i][j] == d[i + 1][j]) {
      i++;
    } else if (i <= j - 1 && d[i][j] == d[i][j - 1]) {
      j--;
    } else if (i + 1 <= j - 1 && s[i] == s[j] &&
               d[i][j] == d[i + 1][j - 1] + 2) {
      x += s[i];
      y += s[j];
      i++;
      j--;
    } else if (d[i][j] == 1 && i == j) {
      x += s[i];
      break;
    } else if (d[i][j] == 2 && s[i] == s[j]) {
      x += s[i];
      y += s[j];
      break;
    } else {
      break;
    }
  }
  reverse(y.begin(), y.end());
  if (x.size() + y.size() <= 100) {
    printf("%s%s\n", x.c_str(), y.c_str());
    exit(0);
  }
  if ((x.size() + y.size()) % 2 == 1) {
    x.pop_back();
  }
  for (int i = 0; i < 50; i++) {
    printf("%c", x[i]);
  }
  for (int i = 0; i < 50; i++) {
    printf("%c", x[49 - i]);
  }
  puts("");
  return 0;
}