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 N = 2605;
string s, t, q;
map<char, int> d;
int f[N][N], n, y = 100;
deque<char> pr, sf;
int main() {
  cin >> s;
  n = s.length();
  if (n >= 2600) {
    for (char x : s) ++d[x];
    for (char x = 'a'; x <= 'z'; ++x)
      if (d[x] >= 100) {
        for (int j = 0; j < 100; ++j) cout << x;
        return 0;
      }
  }
  for (int i = 0; i < n; ++i) f[i][i] = 1;
  for (int i = 0; i < (n - 1); ++i) f[i][i + 1] = 1 + (s[i] == s[i + 1]);
  for (int i = 2; i < n; ++i)
    for (int j = 0; (j + i) < n; ++j)
      f[j][j + i] = max(max(f[j][j + i - 1], f[j + 1][j + i]),
                        f[j + 1][j + i - 1] + (s[j] == s[j + i]) * 2);
  int l = 0, r = n - 1;
  while (l <= r) {
    while ((l + 1) < n && f[l + 1][r] == f[l][r]) ++l;
    while (r && f[l][r - 1] == f[l][r]) --r;
    pr.push_back(s[l]);
    if (f[l][r] >= 2) sf.push_back(s[r]);
    ++l, --r;
  }
  while (y && (pr.size() || sf.size())) {
    if (y && pr.size()) {
      t.push_back(pr.front());
      pr.pop_front();
      --y;
    }
    if (y && sf.size()) {
      q.push_back(sf.front());
      sf.pop_front();
      --y;
    }
  }
  reverse(q.begin(), q.end());
  cout << t << q;
  return 0;
}