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>
char s[50005], t[2505];
int d[2605][2605], cnt[26], n;
char v[2605][2605];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) cnt[s[i] - 'a']++;
  int res = -1;
  for (int i = 0; i < 26; i++)
    if (cnt[i] >= 100) res = i;
  if (res >= 0)
    for (int i = 1; i <= 100; i++) printf("%c", 'a' + res);
  else {
    for (int i = 1; i <= n; i++) t[i] = s[n - i + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (s[i] == t[j]) d[i][j] = d[i - 1][j - 1] + 1, v[i][j] = 1;
        if (d[i][j] < d[i][j - 1]) d[i][j] = d[i][j - 1], v[i][j] = 2;
        if (d[i][j] < d[i - 1][j]) d[i][j] = d[i - 1][j], v[i][j] = 3;
      }
    }
    int x = n, y = n, z = 0;
    char S[105] = {
        0,
    };
    while (v[x][y]) {
      if (v[x][y] == 1)
        S[++z] = s[x], x--, y--;
      else if (v[x][y] == 2)
        y--;
      else
        x--;
      if (z == 100) break;
    }
    if (z < 100)
      printf("%s", S + 1);
    else {
      for (int i = 1; i <= 50; i++) printf("%c", S[i]);
      for (int i = 50; i >= 1; i--) printf("%c", S[i]);
    }
  }
}