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 inf = 1000000000;
const long long MOD = 1000000007ll;
const long double PI = acos(-1.0);
const long long INF = 2000000000000000000ll;
const long double EPS = 1e-6;
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
T lcm(T a, T b) {
  return a * (b / gcd(a, b));
}
int cnt[30];
int n;
string s;
short dp[2605][2605];
short get(int l, int r) {
  if (l > r) return 0;
  if (l == r) return (short)1;
  if (dp[l][r] != -1) return dp[l][r];
  if (s[l] == s[r]) return dp[l][r] = get(l + 1, r - 1) + 2;
  return dp[l][r] = max(get(l + 1, r), get(l, r - 1));
}
void print(int l, int r, int x) {
  if (x >= 100 || l > r) return;
  if (l == r) {
    cout << s[l];
    return;
  }
  if (s[l] == s[r]) {
    cout << s[l];
    print(l + 1, r - 1, x + 2);
    cout << s[l];
  } else {
    if (dp[l + 1][r] > dp[l][r - 1])
      print(l + 1, r, x);
    else
      print(l, r - 1, x);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  memset(dp, -1, sizeof(dp));
  cin >> s;
  n = s.length();
  if (n >= 2600) {
    int ind = 0;
    for (int i = 0; i < s.length(); i++) {
      cnt[s[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
      if (cnt[i] > cnt[ind]) ind = i;
    }
    for (int i = 0; i < 100; i++) cout << (char)('a' + ind);
  } else {
    get(0, n - 1);
    print(0, n - 1, 0);
    cout << endl;
  }
  return 0;
}