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 N = 60000;
vector<int> pos[26];
int dp[N][102], n, pre[N][102], which[N][102];
char s[N];
string ans, spe;
void output(int cur, int how) {
  if (cur == 0) return;
  if (pre[cur][how] == how) {
    output(cur - 1, how);
  } else {
    ans += s[which[cur][how]];
    output(cur - 1, how - 2);
  }
}
int main() {
  ans = "";
  scanf("%s", s + 1);
  n = strlen(s + 1);
  if (n == 1) {
    puts(s + 1);
    return 0;
  }
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= n; i++) {
    pos[s[i] - 'a'].push_back(i);
  }
  dp[0][0] = n + 1;
  for (int i = 0; i < n; i++) {
    int idx = s[i + 1] - 'a';
    for (int j = 0; j <= min(100, n); j++) {
      int cur = dp[i][j];
      if (dp[i + 1][j] < dp[i][j]) {
        dp[i + 1][j] = dp[i][j];
        pre[i + 1][j] = j;
        which[i + 1][j] = -1;
      }
      int where = lower_bound(pos[idx].begin(), pos[idx].end(), cur) -
                  pos[idx].begin() - 1;
      if (where == -1 || pos[idx][where] <= i + 1) continue;
      where = pos[idx][where];
      if (dp[i + 1][j + 2] < where) {
        dp[i + 1][j + 2] = where;
        pre[i + 1][j + 2] = j;
        which[i + 1][j + 2] = i + 1;
      }
    }
  }
  int most = 0, reci = -1, recj = -1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= min(n, 100); j++) {
      if (dp[i][j] > 0) {
        if (dp[i][j] > i + 1) {
          if (most < j + 1 && j + 1 <= 100) {
            most = j + 1, reci = i, recj = j;
          }
        } else {
          if (most < j) {
            most = j, reci = i, recj = j;
          }
        }
      }
    }
  output(reci, recj);
  for (int i = (int)ans.size() - 1; i >= 0; i--) cout << ans[i];
  if (most & 1) {
    ans = s[reci + 1] + ans;
  }
  cout << ans << endl;
  return 0;
}