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 max_n = 100005;
int n;
char a[max_n];
int F[max_n][26];
bool dp[max_n][105][2], used[max_n][105];
int ft[max_n][105][2];
int main() {
  scanf("%s", a);
  while (a[n] != '\0') n++;
  for (int i = 0; i < 26; i++) F[0][i] = -1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) F[i][j] = F[i - 1][j];
    F[i][(int)(a[i - 1] - 'a')] = i - 1;
  }
  int res = 0;
  int ri = 0, rp = 0, rj = 0;
  string rs = "";
  rs += a[0];
  for (int i = 0; i < n; i++) {
    dp[i][0][0] = 1;
    ft[i][0][0] = n;
    for (int j = 1; j <= min(50, min(i, n - i)); j++) {
      if (dp[i - 1][j - 1][0]) {
        int k = ft[i - 1][j - 1][0];
        if (F[k][a[i - 1] - 'a'] > i - 1) {
          dp[i][j][0] = 1;
          ft[i][j][0] = F[k][a[i - 1] - 'a'];
          used[i][j] = 1;
          if (res < 2 * j) {
            res = max(res, 2 * j);
            ri = i;
            rj = j;
            rp = 0;
          }
          if (ft[i][j][0] > i)
            if (res < 2 * j + 1 and 2 * j + 1 <= 100) {
              res = max(res, 2 * j + 1);
              ri = i;
              rj = j;
              rp = 1;
            }
        }
        if (dp[i - 1][j][0] and ft[i - 1][j][0] > ft[i][j][0]) {
          dp[i][j][0] = 1;
          ft[i][j][0] = max(ft[i][j][0], ft[i - 1][j][0]);
          used[i][j] = 0;
        }
      }
    }
  }
  if (res > 1) {
    rs = "";
    string t1 = "";
    for (int i = ri; i > 0; i--)
      if (used[i][rj]) {
        rj--;
        t1 += a[i - 1];
      }
    for (int i = t1.size() - 1; i >= 0; i--) rs += t1[i];
    if (rp == 1) {
      string t = rs;
      t += a[ri];
      rs = t + t1;
    } else
      rs = rs + t1;
  }
  cout << rs << "\n";
  return 0;
}