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 N = 100000 + 10;
const double eps = 1e-8;
const double pi = acos(-1.0);
char s[N];
bool okay[N];
int pre[N][150];
int f[N][51], sel[N][51];
int last[150];
int n;
void draw() {
  for (int i = 1; i < n; ++i)
    if (okay[i]) printf("%c", s[i]);
  puts("");
}
void go(int a, int b) {
  if (b == 0) return;
  if (sel[a][b] == -1) okay[f[a][b]] = okay[a] = 1;
  go(a - 1, b + sel[a][b]);
}
int main() {
  int i, j;
  scanf("%s", s + 1);
  s[0] = '1';
  n = strlen(s);
  if (n == 2) {
    printf("%c\n", s[1]);
    return 0;
  }
  for (i = 1; i <= n; ++i) {
    for (char ch = 'a'; ch <= 'z'; ++ch) pre[i][ch] = last[ch];
    if (i < n) last[s[i]] = i;
  }
  f[1][0] = n;
  f[1][1] = pre[n][s[1]];
  sel[1][1] = -1;
  for (i = 2; i < n; ++i) {
    f[i][0] = n;
    for (j = 1; j <= 50; ++j) {
      if (pre[f[i - 1][j - 1]][s[i]] > f[i][j]) {
        f[i][j] = pre[f[i - 1][j - 1]][s[i]];
        sel[i][j] = -1;
      }
      if (f[i - 1][j] > f[i][j]) {
        f[i][j] = f[i - 1][j];
        sel[i][j] = 0;
      }
    }
    if (f[i][50] > i) {
      go(i, 50);
      draw();
      return 0;
    }
  }
  for (i = 49; i >= 0; --i) {
    for (j = 1; j < n; ++j)
      if (f[j][i] > j + 1) {
        go(j, i);
        if (f[j][i] > j + 1) okay[j + 1] = 1;
        draw();
        return 0;
      }
    for (j = 1; j < n; ++j)
      if (f[j][i] > j) {
        go(j, i);
        if (f[j][i] > j + 1) okay[j + 1] = 1;
        draw();
        return 0;
      }
  }
  return 0;
}