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;
char str[50008], ans[100];
int len, dp[2700][2700], ans0;
void dfs(int l, int r) {
  if (ans0 >= 50) return;
  if (l == r)
    printf("%c", str[l]);
  else if (l + 1 == r && str[l] == str[r]) {
    printf("%c", str[l]);
    ans[ans0++] = str[l];
  } else if (str[l] == str[r]) {
    printf("%c", str[l]);
    ans[ans0++] = str[l];
    dfs(l + 1, r - 1);
  } else {
    if (dp[l + 1][r] > dp[l][r - 1])
      dfs(l + 1, r);
    else
      dfs(l, r - 1);
  }
  return;
}
int main() {
  int i, j, cou[30];
  scanf("%s", str);
  len = strlen(str);
  if (len >= 2600) {
    memset(cou, 0, sizeof(cou));
    for (i = 0; i < len; i++) cou[str[i] - 'a']++;
    for (i = 0; i < 26; i++)
      if (cou[i] >= 100) break;
    for (j = 0; j < 100; j++) printf("%c", i + 'a');
  } else if (len == 1)
    printf("%c", str[0]);
  else if (len == 2) {
    if (str[0] == str[1])
      printf("%s", str);
    else
      printf("%c", str[0]);
  } else {
    for (i = 0; i < len; i++) dp[i][i] = 1;
    for (i = 0; i < len - 1; i++) {
      if (str[i] == str[i + 1])
        dp[i][i + 1] = 2;
      else
        dp[i][i + 1] = 1;
    }
    for (i = 3; i <= len; i++)
      for (j = 0; j <= len - i; j++) {
        if (str[j] == str[j + i - 1])
          dp[j][j + i - 1] = 2 + dp[j + 1][j + i - 2];
        else
          dp[j][j + i - 1] = max(dp[j + 1][j + i - 1], dp[j][j + i - 2]);
      }
    ans0 = 0;
    dfs(0, len - 1);
    for (i = ans0 - 1; i >= 0; i--) printf("%c", ans[i]);
  }
  return 0;
}