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 maxn = 4e3 + 10;
int arr[100], dp[maxn][maxn], n;
pair<int, int> par[maxn][maxn];
string s, ans = "";
void cal_dp() {
  for (int i = 0; i < n; i++) dp[i][i + 1] = 1;
  for (int i = n - 1; i >= 0; i--)
    for (int j = i + 2; j <= n; j++) {
      if (s[i] == s[j - 1] && dp[i][j] < dp[i + 1][j - 1] + 2)
        dp[i][j] = dp[i + 1][j - 1] + 2, par[i][j] = {1, 1};
      if (dp[i][j] < dp[i + 1][j]) dp[i][j] = dp[i + 1][j], par[i][j] = {1, 0};
      if (dp[i][j] < dp[i][j - 1]) dp[i][j] = dp[i][j - 1], par[i][j] = {0, 1};
    }
}
int main() {
  cin >> s;
  n = s.size();
  for (int i = 0; i < n; i++) arr[s[i] - 'a']++;
  for (int i = 0; i < 26; i++)
    if (arr[i] >= 100) {
      for (int j = 0; j < 100; j++) cout << (char)(i + 'a');
      cout << endl;
      return 0;
    }
  cal_dp();
  int len = 0, l = 0, r = n;
  while (l + 1 < r) {
    if (len == 100) break;
    auto tmp = par[l][r];
    if (par[l][r] == make_pair(1, 1)) ans += s[l], len += 2;
    l += tmp.first, r -= tmp.second;
  }
  cout << ans;
  if (len != 100 && l + 1 == r) cout << s[l];
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}