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 long long N = 3005;
string str, ans;
long long cnt[26], dp[N][N];
void go(long long l, long long r) {
  if (l > r || ans.size() == 50) return;
  if (str[l] == str[r]) {
    ans += str[l];
    go(l + 1, r - 1);
    return;
  }
  if (dp[l + 1][r] > dp[l][r - 1]) {
    go(l + 1, r);
    return;
  }
  go(l, r - 1);
  return;
}
long long run(long long l, long long r) {
  if (l > r) return 0;
  long long &res = dp[l][r];
  if (res) return res;
  if (l == r) return res = 1;
  if (str[l] == str[r]) return res = run(l + 1, r - 1) + 2;
  return res = max(run(l + 1, r), run(l, r - 1));
}
int main() {
  long long n, i, j, l, r;
  cin >> str;
  n = str.size();
  for (auto &x : str) cnt[x - 'a']++;
  for (i = 0; i < 26; i++) {
    if (cnt[i] >= 100) {
      for (j = 0; j < 100; j++) cout << (char)(i + 'a');
      cout << "\n";
      return 0;
    }
  }
  run(0, n - 1);
  go(0, n - 1);
  cout << ans;
  reverse(ans.begin(), ans.end());
  if (dp[0][n - 1] <= 100 && ans.size() * 2 != dp[0][n - 1]) ans.erase(0, 1);
  cout << ans << "\n";
  return 0;
}