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;
char mas[50000];
int d[3000][3000];
int c[3000][3000][2];
int n;
int f;
char ans[128];
void prnt(int x, int y) {
  int t;
  int cnt = 0;
  stack<char> s;
  while (x <= y) {
    if (d[x][y] == 1) {
      if (!f) ans[cnt++] = mas[c[x][y][0]];
    } else {
      ans[cnt++] = mas[c[x][y][0]];
      s.push(mas[c[x][y][1]]);
    }
    t = c[x][y][0] + 1;
    y = c[x][y][1] - 1;
    x = t;
  }
  while (!s.empty()) {
    ans[cnt++] = s.top();
    s.pop();
  }
  printf("%s\n", ans);
}
int main() {
  scanf("%s", mas);
  n = strlen(mas);
  for (int i = 0; i < min(n, 3000); i++) {
    d[i][i] = 1;
    c[i][i][0] = c[i][i][1] = i;
    for (int j = i - 1; j >= 0; j--) {
      if (d[j + 1][i] >= d[j][i - 1]) {
        d[j][i] = d[j + 1][i];
        c[j][i][0] = c[j + 1][i][0];
        c[j][i][1] = c[j + 1][i][1];
      } else {
        d[j][i] = d[j][i - 1];
        c[j][i][0] = c[j][i - 1][0];
        c[j][i][1] = c[j][i - 1][1];
      }
      if (mas[j] == mas[i]) {
        if (d[j][i] < d[j + 1][i - 1] + 2) {
          d[j][i] = d[j + 1][i - 1] + 2;
          c[j][i][0] = j;
          c[j][i][1] = i;
        }
      }
      if (d[j][i] >= 100) {
        f = 1;
        prnt(j, i);
        return 0;
      }
    }
  }
  prnt(0, n - 1);
  return 0;
}