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>
int N;
char s[50010];
int c[30];
int dp[2605][2605];
char t[105];
int main() {
  scanf("%s", s);
  N = strlen(s);
  if (N > 2600) {
    for (int i = 0; i < N; i++) c[s[i] - 'a']++;
    for (int j = 0; j < 26; j++) {
      if (c[j] >= 100) {
        for (int k = 0; k < 100; k++) printf("%c", 'a' + j);
        return 0;
      }
    }
  } else {
    for (int b = 0; b < N; b++) dp[b][b + 1] = 1;
    for (int l = 2; l <= N; l++) {
      for (int b = 0; b + l <= N; b++) {
        dp[b][b + l] = std::max(dp[b + 1][b + l], dp[b][b + l - 1]);
        if (s[b] == s[b + l - 1])
          dp[b][b + l] = std::max(dp[b][b + l], dp[b + 1][b + l - 1] + 2);
      }
    }
    t[std::min(dp[0][N], 100)] = '\0';
    int b = 0, e = N;
    int x = 0, y = std::min(dp[0][N], 100) - 1;
    int c = 0;
    while (c < 100 && b < e) {
      if (b + 1 == e) {
        t[x++] = s[b++];
        c++;
      } else if (s[b] == s[e - 1]) {
        t[x++] = s[b++];
        t[y--] = s[(e--) - 1];
        c += 2;
      } else if (dp[b][e - 1] > dp[b + 1][e]) {
        e--;
      } else {
        b++;
      }
    }
    printf("%s\n", t);
  }
}