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>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
const int L = 256;
const int L1 = 'a';
const int L2 = 'z';
bool fin = false;
map<pair<int, int>, string> buf;
char sss[200] = {0};
string work(int q, int l, int r, vector<vector<int> > &ll,
            vector<vector<int> > &rr, string &s) {
  if (l > r) return "";
  if (buf.count(make_pair(l, r)) > 0) return buf[make_pair(l, r)];
  if (q == 50) {
    fin = true;
    return "";
  }
  int ql, qr;
  string ss = "", s2;
  for (int i = L1; i <= L2; i++) {
    ql = rr[l][i];
    qr = ll[r][i];
    if (ql != -1 && qr != -1 && ql <= r && qr >= l && ql <= qr) {
      if (ql == qr)
        s2 = s[ql];
      else if (ql < qr) {
        sss[q] = s[ql];
        s2 = s[ql] + work(q + 1, ql + 1, qr - 1, ll, rr, s) + s[qr];
        if (2 * q + s2.length() >= 100) {
          fin = true;
          return s2;
        }
        if (fin) return s2;
        sss[q] = 0;
      }
      if (ss.length() < s2.length()) ss = s2;
    }
  }
  buf[make_pair(l, r)] = ss;
  return ss;
}
int main() {
  ios_base::sync_with_stdio(false);
  string s;
  cin >> s;
  int n = s.length();
  vector<vector<int> > ll(n, vector<int>(L, -1));
  vector<vector<int> > rr(n, vector<int>(L, -1));
  for (long long i = 0; i < n; i++) {
    if (i > 0)
      for (long long j = 0; j < L; j++) ll[i][j] = ll[i - 1][j];
    ll[i][s[i]] = i;
  }
  for (long long i = n - 1; i >= 0; i--) {
    if (i < n - 1)
      for (long long j = 0; j < L; j++) rr[i][j] = rr[i + 1][j];
    rr[i][s[i]] = i;
  }
  string ss = work(0, 0, n - 1, ll, rr, s);
  if (ss.length() > 100) {
    for (long long i = 0; i < 50; i++) cout << ss[i];
    for (long long i = 50 - 1; i >= 0; i--) cout << ss[i];
  } else
    cout << ss;
}