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 long long int N = 200001;
const long long int M = 21;
struct point {
  long long int x, y, cur;
  bool operator==(const point b) {
    if (this->x == b.x && this->y == b.y) return 1;
    return 0;
  }
  bool operator!=(const point b) { return !(*this == b); }
  friend bool operator<(const point a, const point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
  }
};
void debug(stringstream &s) {}
template <typename T, typename... Args>
void debug(stringstream &s, T a, Args... args) {
  string word;
  s >> word;
  cout << word << " = " << a << endl;
  debug(s, args...);
}
bool overflow;
long long int fast_exp(long long int x, long long int n) {
  if (n == 0) return 1;
  long long int ans;
  if (n % 2 == 0) {
    ans = fast_exp(x, n / 2);
    if (ans > ans * ans % 998244353) overflow = 1;
    ans = ans * ans % 998244353;
  } else {
    ans = fast_exp(x, n - 1);
    if (ans > ans * x % 998244353) overflow = 1;
    ans = ans * x % 998244353;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int _ = 1;
  while (_--) {
    long long int n, m = 0, x = 0, y = 0, ans = 0, k;
    string s, sol;
    cin >> s;
    n = s.size();
    set<long long int, greater<long long int>> c[26];
    s = '0' + s;
    for (int i = 1; i <= n; i++) c[s[i] - 'a'].insert(i);
    long long int dp[n + 1][51];
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= n; i++) dp[i][0] = n + 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j < 51; j++) {
        dp[i][j] = dp[i - 1][j];
        x = dp[i - 1][j - 1];
        auto it = c[s[i] - 'a'].upper_bound(x);
        if (it != c[s[i] - 'a'].end() && *it >= i) {
          dp[i][j] = max(dp[i][j], *it);
        }
      }
    }
    x = -1;
    for (int i = 50; i > 0; i--) {
      bool flag = 0;
      m = 0;
      for (int j = 1; j <= n; j++) {
        if (dp[j][i] != -1) {
          if (dp[j][i] - j >= m) {
            x = j;
            y = i;
            m = dp[j][i] - j;
          }
          flag = 1;
        }
      }
      if (flag) break;
    }
    for (int i = x; i > 0; i--) {
      if (dp[i - 1][y] != dp[i][y]) {
        if (dp[i][y] > i)
          sol = s[i] + sol + s[i];
        else
          sol = s[i];
        y--;
      }
    }
    cout << sol << "\n";
  }
  return 0;
}