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 len = 4000;
char s[50004];
char dp[4004][4004];
char p[4004][4004];
char ans[105];
int sz = 0;
int main() {
  scanf("%s", s);
  int n = min((int)strlen(s), len);
  for (int i = 0; i < n; i++) dp[i][i] = 1, p[i][i] = 0;
  for (int i = 0; i < n - 1; i++)
    if (s[i] == s[i + 1])
      dp[i][i + 1] = 2, p[i][i + 1] = 0;
    else
      dp[i][i + 1] = 1, p[i][i + 1] = 1;
  int x = 0, y = 0;
  bool fo = 0;
  for (int i = 2; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[j][j + i] = dp[j + 1][j + i - 1] + (s[j] == s[j + i]) * 2;
      p[j][j + i] = 3;
      if (dp[j][j + i - 1] > dp[j][j + i])
        dp[j][j + i] = dp[j][j + i - 1], p[j][j + i] = 1;
      if (dp[j + 1][j + i] > dp[j][j + i])
        dp[j][j + i] = dp[j + 1][j + i], p[j][j + i] = 2;
      if (dp[j][j + i] >= 100) {
        fo = 1;
        x = j, y = j + i;
        break;
      }
    }
    if (fo) break;
  }
  if (!fo) x = 0, y = n - 1;
  while (true) {
    if (p[x][y] == 3) {
      if (s[x] == s[y]) ans[sz++] = s[x];
      x++, y--;
    } else if (p[x][y] == 2)
      x++;
    else if (p[x][y] == 1)
      y--;
    if (p[x][y] == 0) {
      if (x < y) {
        if (s[x] == s[y]) ans[sz++] = s[x];
        for (int i = sz - 1; i >= 0; i--) ans[sz++] = ans[i];
      } else if (x == y && sz < 50) {
        ans[sz++] = s[x];
        for (int i = sz - 2; i >= 0; i--) ans[sz++] = ans[i];
      } else
        for (int i = sz - 1; i >= 0; i--) ans[sz++] = ans[i];
      break;
    }
  }
  printf("%s\n", ans);
  return 0;
}