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 MAGIC = 2603;
int n;
string s;
int cnt[26];
int dp[MAGIC][MAGIC];
deque<char> dq;
string res;
int sz;
int calc(int l, int r) {
  if (r <= l) return r - l + 1;
  int &ret = dp[l][r];
  if (~ret) return ret;
  ret = 0;
  if (s[l] == s[r]) ret = max(ret, calc(l + 1, r - 1) + 2);
  ret = max(ret, calc(l + 1, r));
  ret = max(ret, calc(l, r - 1));
  return ret;
}
void trace(int l, int r) {
  if (res.size() == (sz + 1) / 2) return;
  if (s[l] == s[r] && calc(l, r) == calc(l + 1, r - 1) + 2) {
    res.push_back(s[l]);
    trace(l + 1, r - 1);
  } else if (calc(l, r) == calc(l + 1, r))
    trace(l + 1, r);
  else
    trace(l, r - 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> s;
  int n = s.size();
  s = '#' + s;
  for (int i = 1; i <= n; ++i) {
    cnt[s[i] - 'a']++;
  }
  for (int c = 0; c < 26; ++c) {
    if (cnt[c] >= 100) {
      for (int i = 0; i < 100; ++i) cout << (char)(c + 'a');
      return 0;
    }
  }
  memset(dp, -1, sizeof dp);
  sz = calc(1, n);
  if (sz > 100) sz = 100;
  trace(1, n);
  cout << res;
  if (sz & 1) res.pop_back();
  reverse(res.begin(), res.end());
  cout << res;
}