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 = 5e4 + 10;
const int R = 50;
char s[N];
int f[N][R + 10], p[N][R + 10];
int last[30];
int pre[N][30];
bool mark[N];
int main() {
  scanf("%s", s);
  int n = strlen(s);
  for (int i = 0; i < n; ++i) s[i] -= 'a';
  for (int j = 0; j < 26; ++j) last[j] = -1;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) pre[i][j] = last[j];
    last[s[i]] = i;
  }
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= R; ++j) f[i][j] = -1, p[i][j] = 0;
  f[0][0] = n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= R; ++j) {
      if (f[i][j] == -1) continue;
      if (f[i][j] > f[i + 1][j]) {
        f[i + 1][j] = f[i][j];
        p[i + 1][j] = 0;
      }
      int ft = pre[f[i][j]][s[i]];
      if (ft > f[i + 1][j + 1]) {
        f[i + 1][j + 1] = ft;
        p[i + 1][j + 1] = 1;
      }
    }
  }
  int mx = 0, mi = -1, mj = -1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= R; ++j) {
      if (f[i][j] >= i - 1) {
        int len = 2 * j;
        if (f[i][j] == i - 1) len--;
        if (len > mx) {
          mx = len;
          mi = i;
          mj = j;
        }
      }
    }
  }
  int j = mj;
  for (int i = mi; i > 0; --i) {
    if (p[i][j] == 1) {
      mark[i - 1] = 1;
      mark[f[i][j]] = 1;
      j--;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (mark[i]) putchar(s[i] + 'a');
  }
  putchar('\n');
  return 0;
}