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 = 1000050;
const int MAXK = 5005;
char s[MAXN];
int n, c[256], dp[MAXK][MAXK], best[MAXK][MAXK];
int main() {
  while (scanf("%s", s) >= 1) {
    memset(c, 0, sizeof c);
    memset(dp, 0, sizeof dp);
    memset(best, -1, sizeof best);
    n = strlen(s);
    bool ok = false;
    for (int i = (0); i < (int)(n); i++) {
      c[s[i] - 'a']++;
      if (c[s[i] - 'a'] >= 100) {
        for (int z = (0); z < (int)(100); z++) {
          printf("%c", s[i]);
        }
        puts("");
        ok = true;
        break;
      }
    }
    if (ok) continue;
    for (int sz = (0); sz < (int)(n); sz++) {
      for (int i = (0); i < (int)(n); i++) {
        int j = i + sz;
        if (j > n) break;
        if (s[i] == s[j]) {
          if (i == j)
            dp[i][j] = 1;
          else
            dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
          best[i][j] = 0;
        }
        if (j - 1 >= 0 && dp[i][j] < dp[i][j - 1]) {
          dp[i][j] = dp[i][j - 1];
          best[i][j] = 1;
        }
        if (i + 1 < n && dp[i][j] < dp[i + 1][j]) {
          dp[i][j] = dp[i + 1][j];
          best[i][j] = 2;
        }
      }
    }
    int l = 0, r = n - 1;
    string a, b;
    while (true) {
      if (l > r) break;
      if (best[l][r] == 0) {
        if (l == r) {
          a.push_back(s[l]);
        } else {
          a.push_back(s[l]);
          b.push_back(s[r]);
          if (((int)a.size()) >= 50) break;
        }
        l++;
        r--;
        continue;
      }
      if (best[l][r] == 1) {
        r--;
        continue;
      }
      if (best[l][r] == 2) {
        l++;
        continue;
      }
      break;
    }
    reverse(b.begin(), b.end());
    printf("%s\n", (a + b).c_str());
  }
  return 0;
}