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 NS = 100000;
const int MS = 3000;
int a[30], res;
int dp[MS][MS], L[MS][MS];
char ch[NS];
string str1, str2;
string getLCS(string s, string ts) {
  string result;
  int n_len = ts.length() + 1;
  int m_len = s.length() + 1;
  for (int i = 0; i < n_len; i++) {
    L[i][0] = 0;
  }
  for (int i = 0; i < m_len; i++) {
    L[0][i] = 0;
  }
  for (int i = 1; i < n_len; i++) {
    for (int j = 1; j < m_len; j++) {
      if (ts[i - 1] == s[j - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1;
      } else {
        L[i][j] = (L[i][j - 1] > L[i - 1][j] ? L[i][j - 1] : L[i - 1][j]);
      }
    }
  }
  int i = n_len - 1;
  int j = m_len - 1;
  while (i > 0 && j > 0) {
    if (ts[i - 1] == s[j - 1]) {
      result = s[j - 1] + result;
      i--;
      j--;
    } else if (L[i - 1][j] >= L[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return result;
}
int main() {
  while (cin >> str1) {
    int len = str1.length();
    memset(a, 0, sizeof(a));
    for (int i = 0; i < len; i++) a[str1[i] - 'a']++;
    for (int i = 0; i < 26; i++)
      if (a[i] >= 100) {
        for (int j = 0; j < 100; j++) printf("%c", 'a' + i);
        puts("");
        return 0;
      }
    for (int i = 0; i < len; i++) ch[i] = str1[len - 1 - i];
    str2 = (string)ch;
    string ans = getLCS(str1, str2);
    len = ans.length();
    if (len > 100) {
      for (int i = 0; i < len; i++) ch[i] = ans[i];
      for (int i = 0; i < 50; i++) printf("%c", ch[i]);
      for (int i = len - 50; i < len; i++) printf("%c", ch[i]);
      puts("");
    } else {
      cout << ans << endl;
    }
  }
  return 0;
}