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:256000000")
using namespace std;
const int INF = 1000000000;
const long long LINF = 4000000000000000000LL;
const double eps = 1e-9;
void prepare() {}
const int maxn = 50100;
string s;
int n;
int dp[maxn][105], fr[maxn][105];
int last[30][maxn];
void read() { getline(cin, s); }
void upd(int &d, int nd, int &f, int dx) {
  if (d < nd) {
    d = nd;
    f = dx;
  }
}
string getOdd() {
  memset((dp), (-1), sizeof(dp));
  memset((fr), (-1), sizeof(fr));
  for (int i = (0); i < ((n)); i++) {
    dp[i + 1][1] = i;
    fr[i + 1][1] = 1;
    dp[i + 1][0] = i + 1;
  }
  for (int i = (0); i < ((n)); i++)
    if (i) {
      int ch = s[i] - 'a';
      for (int j = (0); j < ((101)); j++) {
        upd(dp[i + 1][j], dp[i][j], fr[i + 1][j], 0);
        int si = dp[i][j] - 1;
        if (si >= 0 && last[ch][si] >= 0)
          upd(dp[i + 1][j + 2], last[ch][si], fr[i + 1][j + 2], 2);
      }
    }
  for (int j = (100); j >= (1); j--) {
    if (dp[n][j] >= 0) {
      int bj = j;
      {};
      string ret;
      int i = n;
      while (fr[i][j] >= 0) {
        if (fr[i][j]) ret.push_back(s[i - 1]);
        j -= fr[i][j];
        i--;
      }
      string t = ret;
      if (bj & 1) t.pop_back();
      reverse((t).begin(), (t).end());
      ret += t;
      return ret;
    }
  }
  return "";
}
bool solve() {
  n = (int)(s).size();
  memset((last), (-1), sizeof(last));
  for (int i = (0); i < ((n)); i++) {
    if (i) {
      for (int j = (0); j < ((30)); j++) last[j][i] = last[j][i - 1];
    }
    last[s[i] - 'a'][i] = i;
  }
  printf("%s\n", getOdd().c_str());
  return false;
}
int main() {
  prepare();
  read();
  while (solve())
    ;
  return 0;
}