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;
string s;
stack<char> Ps;
int D[2600][2600];
int charc[256];
int N;
int prec(int l, int r) {
  int &ret = D[l][r];
  if (ret != -1) return ret;
  if (l > r) return ret = 0;
  if (l == r) return ret = 1;
  ret = max(prec(l + 1, r), prec(l, r - 1));
  if (s[l] == s[r]) {
    ret = max(ret, (prec(l + 1, r - 1) + 2));
  }
  return ret;
}
void prn(int l, int r, int counts) {
  if (l > r) return;
  if (counts <= 0) return;
  if (l == r) {
    cout << s[l];
    return;
  }
  if (D[l][r] == D[l + 1][r]) {
    prn(l + 1, r, counts);
    return;
  }
  if (D[l][r] == D[l][r - 1]) {
    prn(l, r - 1, counts);
    return;
  }
  cout << s[l];
  prn(l + 1, r - 1, counts - 2);
  cout << s[r];
}
int main() {
  cin >> s;
  N = s.length();
  if (s.length() > 2600 - 26) {
    for (int i = 'a'; i <= 'z'; i++) charc[i] = 0;
    for (int i = 0; i < N; i++) {
      charc[s[i]]++;
      if (charc[s[i]] == 100) {
        char res[101];
        for (int j = 0; j < 100; j++) res[j] = s[i];
        cout << res;
        return 0;
      }
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) D[i][j] = -1;
  }
  D[0][N - 1] = prec(0, N - 1);
  prn(0, N - 1, 100);
  return 0;
}