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;
template <class T>
inline void smn(T &a, const T &b) {
  if (b < a) a = b;
}
template <class T>
inline void smx(T &a, const T &b) {
  if (b > a) a = b;
}
template <class T>
inline T _rev(const T &a) {
  T _ = a;
  reverse(_.begin(), _.end());
  return _;
}
const double eps = 1e-8;
const long double leps = 1e-14;
const int MN = 5 * 1000 * 10 + 1000;
string s;
int dp[MN][150];
vector<int> pl[100];
int pre(int a, int b) {
  int t = lower_bound(pl[a].begin(), pl[a].end(), b) - pl[a].begin();
  return pl[a][t - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> s;
  s = "@" + s;
  for (int i = 1; i < s.size(); i++) pl[s[i] - 'a'].push_back(i);
  dp[0][0] = s.size();
  for (int i = 1; i <= 100; i++) dp[0][i] = -1;
  for (int i = 1; i < s.size(); i++) {
    for (int j = 0; j <= 100; j++) dp[i][j] = dp[i - 1][j];
    for (int j = 0; j < 100; j += 2) {
      if (dp[i - 1][j] != -1 && dp[i - 1][j] > i) smx(dp[i][j + 1], i);
      if (dp[i - 1][j] != -1 && dp[i - 1][j] > i) {
        int t = pre(s[i] - 'a', dp[i - 1][j]);
        if (t > i) smx(dp[i][j + 2], t);
      }
    }
  }
  int k = 0;
  for (int i = 0; i <= 100; i++)
    if (dp[s.size() - 1][i] != -1) k = i;
  int p = (k - 1) / 2, tmp = k;
  string o;
  o.resize(k, '@');
  for (int i = s.size() - 1; i > 0; i--)
    if (dp[i - 1][k] != dp[i][k]) {
      o[p] = o[tmp - p - 1] = s[i];
      p--;
      if (k % 2 == 1)
        k--;
      else
        k -= 2;
    }
  cout << o << '\n';
  return 0;
}