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 T bigmod(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T bpow(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
int toInt(string s) {
  int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int toLlint(string s) {
  long long int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
char s[50009];
int f[27], n, p[2605][2605];
char np[2605][2605];
int dp(int i, int j) {
  if (i == j) return 1;
  if (i > j) return 0;
  int &pr = p[i][j];
  if (pr != -1) return pr;
  int x;
  pr = 0;
  if (s[i] == s[j]) {
    x = dp(i + 1, j - 1) + 2;
    if (x > pr) {
      np[i][j] = 0;
      pr = x;
    }
  }
  x = dp(i + 1, j);
  if (x > pr) {
    np[i][j] = 1;
    pr = x;
  }
  x = dp(i, j - 1);
  if (x > pr) {
    np[i][j] = 2;
    pr = x;
  }
  return pr;
}
vector<char> rs;
char mx;
void prnt(int i, int j) {
  if (i > j) {
    return;
  }
  if (i == j) {
    mx = s[i];
  } else if (np[i][j] == 0) {
    rs.push_back(s[i]);
    prnt(i + 1, j - 1);
  } else if (np[i][j] == 1)
    prnt(i + 1, j);
  else if (np[i][j] == 2)
    prnt(i, j - 1);
}
int main() {
  int cs = 1, t, i, j;
  memset(f, 0, sizeof(f));
  scanf("%s", s);
  n = strlen(s);
  for (i = 0; i < n; i++) {
    f[s[i] - 'a']++;
  }
  for (i = 0; i < 26; i++) {
    if (f[i] >= 100) {
      for (j = 0; j < 100; j++) printf("%c", 'a' + i);
      return 0;
    }
  }
  memset(p, -1, sizeof(p));
  dp(0, n - 1);
  mx = '.';
  prnt(0, n - 1);
  if (rs.size() == 0)
    printf("%c", s[0]);
  else {
    if (rs.size() >= 50) {
      for (i = 0; i < 50; i++) {
        printf("%c", rs[i]);
      }
      for (i = 49; i > -1; i--) {
        printf("%c", rs[i]);
      }
    } else {
      for (i = 0; i < rs.size(); i++) {
        printf("%c", rs[i]);
      }
      if (mx != '.') printf("%c", mx);
      for (i = rs.size() - 1; i > -1; i--) {
        printf("%c", rs[i]);
      }
    }
  }
  return 0;
}