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>
bool FLAG = 0;
using namespace std;
const long long MOD = (long long)1e9 + 7, N = (long long)1e5 + 222;
const long long INF = (long long)1e18;
string s;
long long cnt[N], dp[3000][3000];
string rec(long long l, long long r) {
  string x = " ";
  x[0] = s[l - 1];
  if (l > r) return "";
  if (l == r) return x;
  if (s[l - 1] == s[r - 1]) {
    x = s[l - 1] + rec(l + 1, r - 1) + s[r - 1];
    return x;
  } else {
    if (dp[l][r] == dp[l + 1][r])
      return rec(l + 1, r);
    else if (dp[l][r] == dp[l][r - 1])
      return rec(l, r - 1);
  }
}
void solve() {
  cin >> s;
  for (long long i = 0; i < (long long)(s.size()); ++i) {
    cnt[s[i] - 'a']++;
  }
  for (long long i = 0; i <= 26; ++i) {
    if (cnt[i] >= 100) {
      for (long long j = 1; j <= 100; ++j) {
        cout << (char)(i + 'a');
      }
      return;
    }
  }
  for (long long i = 1; i <= (long long)(s.size()); ++i) {
    dp[i][i] = 1;
  }
  for (long long len = 1; len <= (long long)(s.size()); ++len) {
    for (long long l = 1; l + len <= (long long)(s.size()); ++l) {
      long long r = l + len;
      if (s[l - 1] == s[r - 1]) {
        dp[l][r] = dp[l + 1][r - 1] + 2;
      }
      dp[l][r] = max(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
    }
  }
  string ans = rec(1, (long long)(s.size()));
  long long l = 0, r = (long long)(ans.size()) - 1;
  long long ok = 0, pos = -1;
  while (r - l + 1 - ok > 100) {
    if ((r - l + 1 - ok) % 2 != 0) {
      pos = (r + l) / 2;
      ok = 1;
    } else {
      l++;
      r--;
    }
  }
  for (long long i = l; i <= r; ++i) {
    if (i == pos) continue;
    cout << ans[i];
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long ttt = 1;
  while (ttt--) {
    solve();
  }
  return 0;
}