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 MAXN = 3005, MAXM = 50005;
int n, x, y, fq[26], dp[MAXN][MAXN];
char a[MAXM], s[MAXM], w[MAXM];
void rec(int i, int j) {
  if (i > j) return;
  if (i == j) {
    w[x++] = s[i];
    return;
  }
  if (s[i] == s[j] && dp[i + 1][j - 1] + 2 == dp[i][j]) {
    w[x++] = s[i], w[y--] = s[j];
    rec(i + 1, j - 1);
  } else if (dp[i][j - 1] == dp[i][j])
    rec(i, j - 1);
  else
    rec(i + 1, j);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    fq[s[i] - 'a' + 1]++;
    if (fq[s[i] - 'a' + 1] == 100) {
      for (int j = 1; j <= 100; j++) printf("%c", s[i]);
      printf("\n");
      return 0;
    }
  }
  memset(dp, -1, sizeof(dp));
  for (int i = 1; i <= n; i++) dp[i][i] = 1, dp[i + 1][i] = 0;
  for (int l = 1; l < n; l++) {
    for (int i = 1; i + l <= n; i++) {
      int j = i + l;
      int ans = max(dp[i][j - 1], dp[i + 1][j]);
      if (s[i] == s[j] && dp[i + 1][j - 1] != -1)
        ans = max(ans, dp[i + 1][j - 1] + 2);
      dp[i][j] = ans;
    }
  }
  x = 1, y = dp[1][n];
  rec(1, n);
  if (dp[1][n] <= 100) {
    printf("%s\n", w + 1);
    return 0;
  }
  int t = dp[1][n], q;
  for (int i = 1; i <= t / 2; i++) {
    a[i] = w[i];
    q = i;
    if (abs(2 * i - 100) <= 1) break;
  }
  for (int i = q + 1, j = q; i <= 100; i++, j--) a[i] = a[j];
  printf("%s", a + 1);
  return 0;
}