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;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
string s;
int cnt[30];
int dp[3005][3005];
int main() {
  cin >> s;
  int n = (int)(s).size();
  if (n >= 3000) {
    memset((cnt), (0), sizeof(cnt));
    int ans = 0;
    for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'];
    for (int i = 0; i < 30; ++i)
      if (cnt[i] > cnt[ans]) ans = i;
    for (int i = 0; i < 100; ++i) cout << char(ans + 'a');
    return 0;
  }
  int x = 0, y = 0;
  for (int i = 0; i < n; ++i) dp[i][i] = 1;
  for (int i = 0; i < n - 1; ++i) {
    dp[i][i + 1] = max(1, 2 * (s[i] == s[i + 1]));
    if (dp[i][i + 1] > dp[x][y]) x = i, y = i + 1;
  }
  for (int i = n - 2; i >= 0; --i)
    for (int j = i + 2; j < n; ++j) {
      dp[i][j] = max(dp[i + 1][j - 1] + 2 * (s[i] == s[j]),
                     max(dp[i + 1][j], dp[i][j - 1]));
      if (dp[i][j] > dp[x][y]) x = i, y = j;
    }
  string ans;
  for (;;) {
    if (x == y or (y - x == 1 and s[x] == s[y]) or
        2 * (int)(ans).size() == 100) {
      string rans = ans;
      reverse((rans).begin(), (rans).end());
      if (2 * (int)(ans).size() == 100)
        ans += rans;
      else if (x == y)
        ans = ans + s[x] + rans;
      else
        ans = ans + s[x] + s[x] + rans;
      break;
    }
    int i = x + 1, j = y - 1;
    int cur = dp[x + 1][y - 1] + 2 * (s[x] == s[y]);
    if (dp[x + 1][y] > cur) cur = dp[x + 1][y], i = x + 1, j = y;
    if (dp[x][y - 1] > cur) cur = dp[x][y - 1], i = x, j = y - 1;
    if (i == x + 1 and j == y - 1 and s[x] == s[y]) ans += s[x];
    x = i, y = j;
  }
  cout << ans << endl;
  return 0;
}