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 + 500;
char s[N], ans[105];
int nx[N][26], lst[26], f[N][105], st[N][105], pre[N][105];
int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j <= 25; j++) nx[i][j] = lst[j];
    lst[s[i] - 'a'] = i;
  }
  memset(f, 0x7f, sizeof(f));
  for (int i = 1; i <= n; i++) {
    f[i][0] = f[i][1] = i;
    st[i][0] = st[i][1] = i;
    pre[i][0] = pre[i][1] = 0;
  }
  for (int i = n - 1; i >= 1; i--) {
    if (f[i + 1][2] != 0x7f7f7f7f) {
      f[i][2] = f[i + 1][2];
      st[i][2] = st[i + 1][2];
      pre[i][2] = pre[i + 1][2];
    }
    int t = nx[i][s[i] - 'a'];
    if (t && t < f[i][2]) {
      f[i][2] = t;
      st[i][2] = i;
      pre[i][2] = 0;
    }
  }
  for (int i = n - 1; i >= 1; i--) {
    for (int j = 3; j <= min(n - i + 1, 100); j++) {
      if (f[i + 1][j] != 0x7f7f7f7f) {
        f[i][j] = f[i + 1][j];
        st[i][j] = st[i + 1][j];
        pre[i][j] = pre[i + 1][j];
      }
      if (f[i + 1][j - 2] != 0x7f7f7f7f) {
        int tmp = nx[f[i + 1][j - 2]][s[i] - 'a'];
        if (tmp && tmp < f[i][j]) {
          f[i][j] = tmp;
          st[i][j] = i;
          pre[i][j] = st[i + 1][j - 2];
        }
      }
    }
  }
  int t, i, j;
  for (t = 101; f[1][t] > n; --t)
    ;
  for (i = 0, j = 1; j; j = pre[j][t], t -= 2) ans[i++] = s[st[j][t]];
  for (j = 0; j < i; ++j) putchar(ans[j]);
  for (i = i - 1 + t; i >= 0; i--) putchar(ans[i]);
  return 0;
}