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 int MAX_N = 50000 + 10, MAX_LEN = 100 + 3, INF = ~0U >> 2;
int dp[MAX_N][MAX_LEN];
int pr[MAX_N][MAX_LEN];
int nxt[MAX_N][26];
int n;
string s;
int main() {
  cin >> s;
  n = s.size();
  fill(nxt[n], nxt[n] + 26, INF);
  for (int i = n - 1; i >= 0; --i) {
    memcpy(nxt[i], nxt[i + 1], sizeof nxt[i]);
    nxt[i][s[i] - 'a'] = i;
  }
  for (int i = 0; i < n; ++i) {
    dp[i][0] = i;
    dp[i][1] = i + 1;
    dp[i][2] = nxt[i + 1][s[i] - 'a'] + 1;
  }
  for (int j = 3; j <= 100; ++j) {
    int minRight = INF, by = -1;
    for (int i = n - 1; i >= 0; --i) {
      if (minRight < INF) {
        dp[i][j] = nxt[minRight][s[i] - 'a'] + 1;
        pr[i][j] = by;
      } else
        dp[i][j] = INF;
      if (dp[i][j - 2] < minRight) {
        minRight = dp[i][j - 2];
        by = i;
      }
    }
  }
  int bj, bi;
  for (int j = 100; j >= 1; --j) {
    for (int i = 0; i < n; ++i)
      if (dp[i][j] < INF) {
        bj = j, bi = i;
        goto out;
      }
  }
out : {}
  string t = "";
  while (bj >= 2) {
    t += s[bi];
    bi = pr[bi][bj];
    bj -= 2;
  }
  string rev = t;
  reverse(rev.begin(), rev.end());
  string ans = t;
  if (bj == 1) ans += s[bi];
  ans += rev;
  cout << ans << endl;
}