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 str[50010];
int f[3000][3000];
pair<int, int> path[3000][3000];
int c[26], n;
bool mk[3000];
void go(int a, int b) {
  if (a == 0 && b == 0) return;
  go(path[a][b].first, path[a][b].second);
  if (path[a][b].first + 1 == a && path[a][b].second + 1 == b) {
    mk[a - 1] = mk[n - b] = true;
  }
}
int main() {
  while (~scanf("%s", str)) {
    n = strlen(str);
    memset(c, 0, sizeof(c));
    for (int i = 0; i < (n); i++) c[str[i] - 'a']++;
    bool flag = false;
    for (int i = 0; i < (26); i++)
      if (c[i] >= 100) {
        flag = true;
        for (int j = 0; j < (100); j++) {
          cout << (char)('a' + i);
        }
        cout << endl;
        break;
      }
    if (flag) continue;
    memset(f, 0, sizeof(f));
    int a = -1, b = -1;
    for (int i = 0; i < (n); i++) {
      for (int j = 0; j < (n - i); j++) {
        if (str[i] == str[n - 1 - j]) {
          if (i == n - 1 - j) {
            f[i + 1][j + 1] = f[i][j] + 1;
          } else {
            f[i + 1][j + 1] = f[i][j] + 2;
          }
          path[i + 1][j + 1] = make_pair(i, j);
        } else {
          if (f[i][j + 1] > f[i + 1][j]) {
            f[i + 1][j + 1] = f[i][j + 1];
            path[i + 1][j + 1] = make_pair(i, j + 1);
          } else {
            f[i + 1][j + 1] = f[i + 1][j];
            path[i + 1][j + 1] = make_pair(i + 1, j);
          }
        }
        if (a == -1 && b == -1 || f[a][b] < f[i + 1][j + 1]) {
          a = i + 1;
          b = j + 1;
        }
      }
    }
    memset(mk, 0, sizeof(mk));
    if (f[a][b] > 100) {
      for (int i = 0; i < (n); i++) {
        for (int j = 0; j < (n - i); j++)
          if (f[i + 1][j + 1] == 100) {
            flag = true;
            go(i + 1, j + 1);
            break;
          }
        if (flag) break;
      }
    } else
      go(a, b);
    for (int i = 0; i < (n); i++)
      if (mk[i]) cout << str[i];
    cout << endl;
  }
  return 0;
}