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 MAXN = 1e9;
template <typename T>
void read(vector<T>& a) {
  for (int i = 0; i < a.size(); ++i) cin >> a[i];
}
template <typename T>
void print(vector<T>& a) {
  for (int i = 0; i < a.size(); ++i) cout << a[i] << " ";
  cout << endl;
}
const int N = 2700;
vector<vector<int> > dp(N, vector<int>(N, -1));
int go(string& s, int l, int r) {
  if (l > r) return 0;
  if (l == r) {
    return 1;
  }
  if (dp[l][r] != -1) return dp[l][r];
  if (s[l] == s[r]) {
    dp[l][r] = go(s, l + 1, r - 1) + 2;
  } else {
    int t1 = go(s, l + 1, r);
    int t2 = go(s, l, r - 1);
    if (t1 > t2) {
      dp[l][r] = t1;
    } else {
      dp[l][r] = t2;
    }
  }
  return dp[l][r];
}
string go_back(string& s, int l, int r) {
  if (l > r) {
    string t = "";
    return t;
  }
  if (l == r) {
    string t = "";
    t += s[l];
    return t;
  }
  if (s[l] == s[r]) {
    string tmp = go_back(s, l + 1, r - 1);
    string tmp2 = "";
    tmp2 += s[l];
    tmp2 += tmp;
    tmp2 += s[r];
    return tmp2;
  } else if (dp[l + 1][r] > dp[l][r - 1]) {
    return go_back(s, l + 1, r);
  } else {
    return go_back(s, l, r - 1);
  }
}
void write() {
  string s;
  cin >> s;
  int l = 0, r = s.length() - 1;
  if (s.length() < 2600) {
    go(s, l, r);
    pair<int, int> mx = {-1, -1};
    for (int i = 0; i < s.length(); ++i) {
      for (int j = 0; j < s.length(); ++j) {
        if (mx.first == -1 || dp[mx.first][mx.second] < dp[i][j]) {
          mx.first = i;
          mx.second = j;
        }
        if (dp[i][j] >= 100) {
          string t = go_back(s, l, r);
          cout << t.substr(0, 50) << t.substr(t.length() - 50, t.length())
               << endl;
          return;
        }
      }
    }
    string t = go_back(s, l, r);
    cout << t << endl;
  } else {
    for (int i = 0; i < 100; ++i) cout << 'a';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  write();
  return 0;
}