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 double eps = 0.000000000000001;
string convertstring(long long n) {
  stringstream ss;
  ss << n;
  return ss.str();
}
char s[100005];
vector<int> v[30];
int dp[2700][2700], n;
pair<int, int> where[2700][2700];
int solve(int left, int right) {
  if (left > right || left >= n) return 0;
  int &ans = dp[left][right];
  if (ans != -1) return ans;
  ans = solve(left + 1, right);
  where[left][right] = make_pair(left + 1, right);
  int x = *(
      (--lower_bound(v[s[left] - 'a'].begin(), v[s[left] - 'a'].end(), right)));
  int ad = 2;
  if (left == x) ad = 1;
  if (left <= x) {
    int y = ad + solve(left + 1, x);
    if (y > ans) {
      ans = y;
      where[left][right] = make_pair(left + 1, x);
    }
  }
  return ans;
}
int main() {
  memset(dp, -1, sizeof(dp));
  ;
  scanf("%s", s);
  int len = strlen(s);
  n = min(2700 - 1, len);
  for (int i = 0; i < n; ++i) {
    v[s[i] - 'a'].push_back(i);
  }
  int xxx = solve(0, n);
  int left = 0, right = n, f = 0, p = 0;
  char ans[1000];
  int lll = 0;
  while (left <= right) {
    pair<int, int> x = where[left][right];
    if (x.second == right) {
      left++;
    } else {
      lll += 2;
      ans[p++] = s[left];
      left++;
      right = x.second;
      if (left > right) f = 1;
      if (lll >= 100) break;
    }
  }
  int to = p - 1;
  if (f) to = p - 2;
  for (; to >= 0; to--, p++) ans[p] = ans[to];
  ans[p] = '\0';
  int len2 = strlen(ans);
  printf("%s\n", ans);
  return 0;
}