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 memo[2700][2700];
string S;
int N;
int doit(int lo, int hi) {
  if (lo == hi) {
    return 1;
  }
  if (lo > hi) {
    return 0;
  }
  int &ret = memo[lo][hi];
  if (ret != -1) return ret;
  ret = 0;
  if (S[lo] == S[hi]) {
    ret = max(ret, doit(lo + 1, hi - 1) + 2);
  }
  ret = max(ret, doit(lo + 1, hi));
  ret = max(ret, doit(lo, hi - 1));
  return ret;
}
string prefixStr, suffixStr, middleStr;
void doitG(int lo, int hi) {
  if (lo == hi) {
    middleStr += S[lo];
    return;
  }
  if (lo > hi) return;
  if (S[lo] == S[hi]) {
    prefixStr += S[lo];
    suffixStr += S[lo];
    doitG(lo + 1, hi - 1);
  } else {
    if (doit(lo + 1, hi) > doit(lo, hi - 1)) {
      doitG(lo + 1, hi);
    } else {
      doitG(lo, hi - 1);
    }
  }
}
int main() {
  cin >> S;
  N = S.size();
  if (N > 2600) {
    for (char c = 'a'; c <= 'z'; c++) {
      int cnt = 0;
      for (int i = 0; i < S.size(); i++) {
        if (S[i] == c) {
          cnt++;
        }
      }
      if (cnt >= 100) {
        for (int i = 0; i < 100; i++) cout << c;
        cout << endl;
        return 0;
      }
    }
    assert(0);
  } else {
    memset(memo, -1, sizeof(memo));
    int ret = doit(0, N - 1);
    prefixStr = suffixStr = middleStr = "";
    doitG(0, N - 1);
    reverse(suffixStr.begin(), suffixStr.end());
    string res = "";
    for (int i = 0; i < prefixStr.size(); i++) res += prefixStr[i];
    for (int i = 0; i < middleStr.size(); i++) res += middleStr[i];
    for (int i = 0; i < suffixStr.size(); i++) res += suffixStr[i];
    if (res.size() < 100) {
      int n = res.size();
      cout << res << endl;
    } else {
      if (res.size() == 100) {
        cout << res << endl;
      } else {
        int n = res.size();
        for (int i = 0; i < 50; i++) cout << res[i];
        for (int j = n - 50; j < n; j++) cout << res[j];
        cout << endl;
      }
    }
  }
  return 0;
}