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;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline string get() {
  char ch[1000010];
  scanf("%s", ch);
  return ch;
}
const int MAX_LG = 21;
const int maxn = 5e4 + 10;
const int state = 1e3 + 10;
const int base = 29;
const int mod = 1e9 + 7;
const int INF = 1e9;
int dp[105];
int maxi[maxn][26];
int res;
pair<int, int> best[maxn], pre[maxn][105];
int32_t main() {
  string s = get();
  int sz = (int)s.size();
  for (int i = 0; i < sz; i++)
    for (int j = 0; j < 26; j++) maxi[i][j] = -5;
  for (int i = 0; i < sz; i++) {
    maxi[i][s[i] - 'a'] = i;
    if (i)
      for (int j = 0; j < 26; j++) maxi[i][j] = max(maxi[i][j], maxi[i - 1][j]);
  }
  for (int i = 0; i <= 100; i++) dp[i] = -5;
  for (int i = 0; i < sz; i++) {
    for (int j = 98; j >= 0; j--) {
      if (dp[j] >= 0 && maxi[dp[j]][s[i] - 'a'] >= 0) {
        if (dp[j + 2] < maxi[dp[j]][s[i] - 'a'] - 1) {
          res = max(res, j + 2);
          best[j + 2] = {maxi[dp[j]][s[i] - 'a'], i};
          pre[i][j + 2] = best[j];
          dp[j + 2] = maxi[dp[j]][s[i] - 'a'] - 1;
        }
      }
    }
    res = max(res, 1);
    dp[1] = i - 1;
    dp[0] = i;
    best[1] = {i, i};
  }
  if (res == 1) return cout << s[0] << "\n", 0;
  assert(res <= 100);
  pair<int, int> now = best[res];
  int cur = res;
  vector<char> ch = {};
  while (cur >= 1) {
    ch.push_back(s[now.first]);
    now = pre[now.second][cur];
    cur -= 2;
  }
  assert(ch.size() <= 50);
  for (int i = 0; i < ch.size(); i++) cout << ch[i];
  reverse(ch.begin(), ch.end());
  for (int i = res % 2; i < ch.size(); i++) cout << ch[i];
}