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;
int n;
char s[50001];
int last[26][50001];
int best[51][50001];
bool prv[51][50001];
void print(int i, int j, int k) {
  int len = 2 * i + (k != -1 ? 1 : 0);
  char ans[101];
  ans[len] = '\0';
  if (k != -1) ans[i] = s[k];
  while (j != 0) {
    if (!prv[i][j]) {
      --j;
      continue;
    }
    --i, --j;
    ans[i] = ans[len - i - 1] = s[j];
  }
  printf("%s\n", ans);
}
void run(int casenr) {
  scanf("%s", s);
  n = strlen(s);
  memset(last, -1, sizeof(last));
  for (int j = (0); j < (n); ++j) {
    int x = s[j] - 'a';
    for (int xx = (0); xx < (26); ++xx) last[xx][j + 1] = last[xx][j];
    last[x][j + 1] = j;
  }
  memset(best, -1, sizeof(best));
  best[0][0] = n;
  prv[0][0] = true;
  for (int i = (0); i < (50); ++i)
    for (int j = (0); j < (n); ++j)
      if (best[i][j] != -1) {
        if (j + 1 <= best[i][j] && best[i][j] > best[i][j + 1]) {
          best[i][j + 1] = best[i][j];
          prv[i][j + 1] = false;
        }
        int x = s[j] - 'a';
        if (last[x][best[i][j]] != -1 && last[x][best[i][j]] >= j + 1 &&
            last[x][best[i][j]] > best[i + 1][j + 1]) {
          best[i + 1][j + 1] = last[x][best[i][j]];
          prv[i + 1][j + 1] = true;
        }
      }
  for (int i = 50; i >= 0; --i) {
    if (i != 50)
      for (int j = (0); j < (n); ++j)
        if (best[i][j] != -1 && j < best[i][j]) {
          print(i, j, j);
          return;
        }
    for (int j = (0); j < (n); ++j)
      if (best[i][j] != -1) {
        print(i, j, -1);
        return;
      }
  }
  assert(false);
}
int main() {
  run(1);
  return 0;
}