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;
int testnum;
vector<long long> nums;
int cnt;
int ans;
char s[50004];
int table[2605][2605], flag[27];
void preprocess() {}
void solve() {
  int ans = -1, left, right, j, i, l, i1, i2;
  if (strlen(s) >= 2600) {
    for (i = 0; i < strlen(s); ++i) flag[s[i] - 'a']++;
    for (i = 0; i < 26; ++i) {
      if (flag[i] >= 100) {
        for (int j = 0; j < 100; ++j) cout << (char)('a' + i);
        break;
      }
    }
    return;
  }
  for (l = 1; l <= strlen(s); ++l) {
    for (i = 0; i <= strlen(s) - l; ++i) {
      j = i + l - 1;
      if (l == 1)
        table[i][j] = 1;
      else if (l == 2) {
        if (s[i] == s[i + 1])
          table[i][j] = 2;
        else
          table[i][j] = 1;
      } else {
        if (s[i] == s[j]) {
          table[i][j] = table[i + 1][j - 1] + 2;
        } else {
          table[i][j] = max(table[i + 1][j], table[i][j - 1]);
        }
      }
      if (table[i][j] >= 100) {
        ans = 100;
        break;
      }
      if (ans < table[i][j]) {
        ans = table[i][j];
        i1 = i;
        i2 = j;
      }
    }
  }
  int m = 0;
  if (ans != 100) {
    i = i1;
    j = i2;
  }
  int rr = ans;
  char result[102];
  while (i <= j && ans) {
    if (s[i] == s[j]) {
      result[m] = s[i];
      result[rr - m - 1] = s[i];
      i++;
      j--;
      m++;
      ans -= 2;
    } else if (table[i + 1][j] > table[i][j - 1]) {
      i++;
    } else {
      j--;
    }
  }
  result[rr] = '\0';
  cout << result << "\n";
}
bool input() {
  scanf("%s", s);
  return true;
}
int main() {
  preprocess();
  int T = 1;
  for (testnum = 1; testnum <= T; testnum++) {
    if (!input()) break;
    solve();
  }
  return 0;
}