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 MAXN = 2600, MAXL = 10000 * 5 + 10, MAXALP = 26;
int n, f[MAXN][MAXN], cnt[MAXALP], p[MAXN][MAXN];
char str[MAXL];
pair<int, int> Tohka;
string Houki;
void Print(const pair<int, int> &a, int res) {
  if (res <= 0) return;
  if (p[a.first][a.second] == -1)
    Print(make_pair(a.first - 1, a.second), res);
  else if (p[a.first][a.second] == 1)
    Print(make_pair(a.first, a.second + 1), res);
  else {
    Print(make_pair(a.first - 1, a.second + 1),
          res - 2 + (a.first == a.second));
    if (res <= 100) Houki += str[a.first];
  }
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  if (n >= 2600) {
    for (int i = 1; i <= n; ++i) ++cnt[str[i] - 'a'];
    for (int i = 0; i < MAXALP; ++i)
      if (cnt[i] >= 100) {
        for (int j = 0; j < 100; ++j) printf("%c", 'a' + i);
        exit(0);
      }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = n; j >= i; --j) {
      f[i][j] = f[i - 1][j], p[i][j] = -1;
      if (f[i][j] < f[i][j + 1]) f[i][j] = f[i][j + 1], p[i][j] = 1;
      if (str[i] == str[j] && f[i][j] < f[i - 1][j + 1] + 1)
        f[i][j] = f[i - 1][j + 1] + 1, p[i][j] = 0;
      if (f[i][j] * 2 - (i == j) >
          f[Tohka.first][Tohka.second] * 2 - (Tohka.first == Tohka.second))
        Tohka = make_pair(i, j);
    }
  Print(Tohka,
        f[Tohka.first][Tohka.second] * 2 - (Tohka.first == Tohka.second));
  string rev =
      Houki.substr(0, Houki.size() - (Tohka.first == Tohka.second &&
                                      f[Tohka.first][Tohka.second] * 2 -
                                              (Tohka.first == Tohka.second) <=
                                          100));
  reverse(rev.begin(), rev.end());
  Houki += rev;
  cout << Houki << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}