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 = 50010;
char s[maxn];
int dp[3][maxn];
int dp2[3100][3100];
int vis[3100][3100];
int tmp;
int dfs(int L, int R) {
  if (L == R) return 1;
  if (L == R + 1) return 0;
  if (vis[L][R]) return dp2[L][R];
  vis[L][R] = 1;
  int &ans = dp2[L][R];
  if (s[tmp + L] == s[tmp + R])
    ans = dfs(L + 1, R - 1) + 2;
  else {
    int a = dfs(L + 1, R), b = dfs(L, R - 1);
    ans = max(a, b);
  }
  return ans;
}
void print(int L, int R, int flag) {
  if (L == R + 1) return;
  if (L == R) {
    if (!flag) printf("%c", s[tmp + L]);
    return;
  }
  if (s[tmp + L] == s[tmp + R]) {
    printf("%c", s[tmp + L]);
    print(L + 1, R - 1, flag);
    printf("%c", s[tmp + R]);
  } else if (dp2[L][R - 1] > dp2[L + 1][R])
    print(L, R - 1, flag);
  else
    print(L + 1, R, flag);
}
int main() {
  scanf("%s", s);
  int n = strlen(s);
  int len = 1;
  for (int i = 0; i < n; i++) {
    dp[0][i] = 0;
    dp[1][i] = 1;
  }
  int a = 0, b = 1, ans = 1;
  while (ans < 100 && len <= n) {
    len++;
    int c = 3 - a - b;
    for (int i = 0; i + len <= n; i++) {
      if (s[i] == s[i + len - 1])
        dp[c][i] = dp[(c + 1) % 3][i + 1] + 2;
      else
        dp[c][i] = max(dp[(c + 2) % 3][i], dp[(c + 2) % 3][i + 1]);
      ans = max(dp[c][i], ans);
    }
    a = (a + 1) % 3;
    b = (b + 1) % 3;
  }
  if (len > n) len--;
  for (int i = 0; i + len <= n; i++)
    if (dp[b][i] == ans) tmp = i;
  memset(vis, 0, sizeof(vis));
  ans = dfs(0, len - 1);
  if (ans <= 100)
    print(0, len - 1, 0);
  else
    print(0, len - 1, 1);
  puts("");
  return 0;
}