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 INF = 999999999;
const long long INFL = 99999999999999999LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;
set<int> pos[30];
int dp[5000][5000], path[5000][5000];
int32_t main() {
  string s;
  cin >> s;
  int n = (int)(s).size();
  for (int i = 0; i < n; i++) {
    pos[s[i] - 'a'].insert(i);
  }
  string pal = "";
  int l = -1, r = n;
  while ((int)(pal).size() < 50 and l + 1 < r) {
    int best = 0, next_l, next_r;
    for (int c = 0; c < 26; c++) {
      set<int>::iterator it = pos[c].lower_bound(l + 1);
      if (it != pos[c].end()) {
        int i = *it;
        it = pos[c].lower_bound(r);
        if (it != pos[c].begin()) {
          it--;
          int j = *it;
          if (j - i + 1 > best) {
            best = j - i + 1;
            next_l = i;
            next_r = j;
          }
        }
      }
    }
    if (next_l == next_r) {
      break;
    }
    pal += string(1, s[next_l]);
    l = next_l;
    r = next_r;
  }
  string Right = pal;
  reverse(Right.begin(), Right.end());
  if ((int)(pal).size() + (int)(Right).size() < 100 and l + 1 < r) {
    pal += string(1, s[l + 1]);
  }
  if ((int)(pal).size() + (int)(Right).size() == 100) {
    cout << pal << Right << endl;
  } else {
    for (int i = 0; i < (int)(s).size(); i++) {
      dp[i][i] = 0;
      path[i][i + 1] = 0;
      dp[i][i + 1] = 1;
      path[i][i + 1] = 1;
    }
    for (int len = 2; len <= (int)(s).size(); len++) {
      for (int l = 0; l + len <= (int)(s).size(); l++) {
        int r = l + len;
        dp[l][r] = 0;
        if (s[l] == s[r - 1] and dp[l + 1][r - 1] + 2 > dp[l][r]) {
          dp[l][r] = dp[l + 1][r - 1] + 2;
          path[l][r] = 1;
        }
        if (dp[l + 1][r] > dp[l][r]) {
          dp[l][r] = dp[l + 1][r];
          path[l][r] = 2;
        }
        if (dp[l][r - 1] > dp[l][r]) {
          dp[l][r] = dp[l][r - 1];
          path[l][r] = 3;
        }
      }
    }
    pal = "";
    int l = 0, r = n;
    while (r - l >= 2) {
      if (path[l][r] == 1) {
        pal += string(1, s[l]);
        l++;
        r--;
      } else if (path[l][r] == 2) {
        l++;
      } else if (path[l][r] == 3) {
        r--;
      }
    }
    string Right = pal;
    reverse(Right.begin(), Right.end());
    if (2 * (int)(pal).size() < 100) {
      if (l < r) {
        pal += string(1, s[l]);
      }
    } else {
      pal = pal.substr(0, 50);
      Right = pal;
      reverse(Right.begin(), Right.end());
    }
    cout << pal << Right << endl;
  }
  return 0;
}