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 i, j, n, m, mx, wi, wj, nx[50005][26], f[50005][52], p[50005][52];
vector<int> a;
char s[50005];
int main() {
  scanf("%s", s);
  n = strlen(s);
  for (j = 0; j < 26; j++) nx[0][j] = -1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < 26; j++) nx[i + 1][j] = nx[i][j];
    nx[i + 1][s[i] - 'a'] = i;
  }
  memset(f, 255, sizeof(f));
  f[0][0] = n;
  for (i = 0; i < n; i++) {
    for (j = 0; j <= 50; j++) {
      if (f[i][j] >= i) {
        if (j + j > mx) {
          mx = j + j;
          wi = i;
          wj = j;
        }
        f[i + 1][j] = max(f[i + 1][j], f[i][j]);
      }
      if (j < 50 && f[i][j] > i) {
        if (j + j + 1 > mx) {
          mx = j + j + 1;
          wi = i;
          wj = j;
        }
        f[i + 1][j + 1] = nx[f[i][j]][s[i] - 'a'];
      }
    }
  }
  for (i = wi, j = wj; i > 0; i--) {
    if (f[i][j] == n) break;
    if (s[i - 1] == s[f[i][j]]) {
      j--;
      a.push_back(i - 1);
    }
  }
  m = a.size();
  m--;
  for (i = m; i >= 0; i--) putchar(s[a[i]]);
  if (mx % 2 == 1) putchar(s[wi]);
  for (i = 0; i <= m; i++) putchar(s[a[i]]);
  return 0;
}