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 buff[50004];
vector<int> pos[26];
int best[102][50004];
int le[102][50004];
int main() {
  int n = strlen(gets(buff));
  for (int i = (0); i < ((n)); i++) pos[buff[i] - 'a'].push_back(i);
  memset(best, -1, sizeof best);
  for (int i = (0); i < ((n)); i++) best[1][i] = le[1][i] = i;
  for (int i = 1; i < n; i++) {
    best[2][i] = best[2][i - 1];
    int c = buff[i] - 'a';
    int lo = 0, hi = pos[c].size() - 1;
    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      if (pos[c][mid] < i)
        lo = mid;
      else
        hi = mid - 1;
    }
    if (pos[c][lo] >= i) continue;
    le[2][i] = pos[c][lo];
    if (best[2][i] == -1 || le[2][best[2][i]] < le[2][i]) best[2][i] = i;
  }
  for (int k = 3; k <= 100; k++) {
    for (int i = k - 1; i < n; i++)
      if (best[k - 2][i - 1] != -1) {
        best[k][i] = best[k][i - 1];
        int b = best[k - 2][i - 1];
        int d = le[k - 2][b];
        int c = buff[i] - 'a';
        int lo = 0, hi = pos[c].size() - 1;
        while (lo < hi) {
          int mid = (lo + hi + 1) >> 1;
          if (pos[c][mid] < d)
            lo = mid;
          else
            hi = mid - 1;
        }
        if (pos[c][lo] >= d) continue;
        le[k][i] = pos[c][lo];
        if (best[k][i] == -1 || le[k][best[k][i]] < le[k][i]) best[k][i] = i;
      }
  }
  for (int L = 100; L >= 1; L--) {
    int ri = -1;
    for (int i = (0); i < ((n)); i++)
      if (best[L][i] != -1) {
        ri = i;
        break;
      }
    if (ri == -1)
      continue;
    else {
      char stk[100];
      int top = 0;
      int level = L;
      while (true) {
        printf("%c", buff[ri]);
        stk[top++] = buff[ri];
        level -= 2;
        if (level < 1) break;
        while (best[level][--ri] != ri)
          ;
      }
      if (L % 2 == 1) top--;
      while (top > 0) printf("%c", stk[--top]);
      printf("\n");
    }
    break;
  }
  return 0;
}