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 RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long INFF = 1LL << 60;
const double EPS = 1e-9;
const double OO = 1e15;
const double PI = acos(-1.0);
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (a < b) a = b;
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
const int N = 2700;
char s[500005];
int cnt[N];
int dp[N][N];
pair<int, int> mem[N][N];
bool out[N];
void output(int l, int r, int last) {
  if (last == 0) return;
  if (l == r) {
    out[l] = 1;
    return;
  }
  if (l > r) return;
  int nextl = mem[l][r].first, nextr = mem[l][r].second;
  if (nextl - l == 1 && r - nextr == 1) {
    out[l] = 1;
    out[r] = 1;
    output(nextl, nextr, last - 2);
  } else
    output(nextl, nextr, last);
}
void solve() {
  int n = strlen(s);
  RST(out);
  RST(cnt);
  for (int i = 0; i < n; ++i) cnt[s[i] - 'a']++;
  for (int i = 0; i < 26; ++i)
    if (cnt[i] >= 100) {
      int x = 100;
      for (int ____n__line__ = x; ____n__line__--;) {
        putchar(i + 'a');
      }
      puts("");
      return;
    }
  RST(dp);
  for (int i = 0; i < n; ++i) dp[i][i] = 1;
  for (int c = 1; c < n; ++c) {
    for (int i = 0; i + c < n; ++i) {
      int j = i + c;
      if (dp[i + 1][j] > dp[i][j]) {
        dp[i][j] = dp[i + 1][j];
        mem[i][j] = make_pair(i + 1, j);
      }
      if (dp[i][j - 1] > dp[i][j]) {
        dp[i][j] = dp[i][j - 1];
        mem[i][j] = make_pair(i, j - 1);
      }
      if (s[i] == s[j] && dp[i + 1][j - 1] + 2 > dp[i][j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
        mem[i][j] = make_pair(i + 1, j - 1);
      }
    }
  }
  int ansmax = -1, l, r;
  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j)
      if (dp[i][j] > ansmax) {
        ansmax = dp[i][j];
        l = i;
        r = j;
      }
  output(l, r, 100);
  for (int i = 0; i < n; ++i)
    if (out[i]) putchar(s[i]);
  puts("");
}
int main() {
  while (~scanf("%s", s)) {
    solve();
  }
}