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 N = 50010;
char str[N];
int cnt[30];
int dp[3000][3000];
char s[N], t[N];
char ans[N];
int la;
void solve(int i, int j) {
  if (i == 0 || j == 0 || la > 55) return;
  if (s[i] == t[j] && dp[i][j] == dp[i - 1][j - 1] + 1) {
    ans[la++] = s[i];
    solve(i - 1, j - 1);
  } else if (dp[i][j] == dp[i - 1][j]) {
    solve(i - 1, j);
  } else {
    solve(i, j - 1);
  }
}
void print(int k) {
  if (la > 50) la = 50;
  for (int i = la - 1; i >= 0; i--) printf("%c", ans[i]);
  if (k != -1) printf("%c", s[k]);
  for (int i = 0; i < la; i++) printf("%c", ans[i]);
  printf("\n");
}
int main() {
  scanf("%s", str);
  memset(cnt, 0, sizeof(cnt));
  int len = strlen(str);
  for (int i = 0; i < len; i++) {
    cnt[str[i] - 97]++;
  }
  for (int i = 0; i < 26; i++)
    if (cnt[i] >= 100) {
      for (int j = 0; j < 100; j++) printf("%c", i + 'a');
      printf("\n");
      return 0;
    }
  int ls = 1, lt = 1;
  for (int i = 0; i < len; i++) {
    s[ls++] = str[i];
    t[lt++] = str[len - i - 1];
  }
  s[ls] = t[lt] = 0;
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= len; i++)
    for (int j = 1; j <= len; j++) {
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      if (s[i] == t[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
    }
  for (int i = 1; i <= len; i++)
    if (dp[i][len - i] >= 50) {
      la = 0;
      solve(i, len - i);
      print(-1);
      return 0;
    }
  int k = -1, s = 0, p, q;
  for (int i = 1; i <= len; i++)
    if (dp[i][len - i] * 2 > s) {
      s = dp[i][len - i] * 2;
      p = i;
      q = len - i;
    }
  for (int i = 1; i <= len; i++) {
    if (dp[i - 1][len - i] * 2 + 1 > s) {
      k = i;
      s = dp[i - 1][len - i] * 2 + 1;
      p = i - 1;
      q = len - i;
    }
  }
  solve(p, q);
  print(k);
  return 0;
}