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;
string str;
int ans[2620][2620];
int main() {
  int count[200];
  memset(count, 0, sizeof count);
  char cans = -1;
  cin >> str;
  for (int j = 0; j < str.size() && cans == -1; j++) {
    count[str[j]]++;
    if (count[str[j]] == 100) cans = str[j];
  }
  if (cans != -1) {
    for (int i = 0; i < 100; i++) printf("%c", cans);
    printf("\n");
  } else {
    int s100 = -1, e100 = -1;
    int e, s;
    ans[0][0] = 1;
    for (int k = 1; k < str.size(); k++) ans[k][k - 1] = 0, ans[k][k] = 1;
    for (int l = 2; l <= str.size(); l++) {
      for (s = 0, e = s + l - 1; e < str.size() && s100 == -1;
           s++, e = s + l - 1) {
        int a = 0, b, c;
        if (str[s] == str[e]) a = ans[s + 1][e - 1] + 2;
        b = ans[s + 1][e], c = ans[s][e - 1];
        ans[s][e] = max(a, max(b, c));
        if (ans[s][e] == 100 || ans[s][e] == 101) s100 = s, e100 = e;
      }
    }
    string pal;
    bool oddflag = 0;
    s = 0, e = str.size() - 1;
    if (s100 != -1) s = s100, e = e100;
    while (s <= e) {
      if (s == e)
        pal += str[e], e--, s++, oddflag = 1;
      else {
        int a = 0, b, c;
        if (str[s] == str[e]) a = ans[s + 1][e - 1] + 2;
        b = ans[s + 1][e], c = ans[s][e - 1];
        if (a > b && a > c)
          pal += str[s], s++, e--;
        else {
          if (b > c)
            s++;
          else if (c > b)
            e--;
          else
            s++;
        }
      }
    }
    string rev = string(pal.rbegin(), pal.rend());
    if (oddflag && s100 != -1)
      rev.erase(0, 1), pal.erase(pal.size() - 1);
    else if (oddflag)
      rev.erase(0, 1);
    pal += rev;
    printf("%s\n", pal.c_str());
  }
}