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 long long inf = 1 << 30;
const int MAXN = 1000 * 1000;
int cnt[26];
char str[MAXN];
int len;
int memo[2601][2601];
int solve(int l, int r) {
  if (l > r) return 0;
  if (l == r) return 1;
  int &ret = memo[l][r];
  if (ret != -1) return ret;
  ret = 0;
  int tmp;
  if (str[l] == str[r]) {
    tmp = solve(l + 1, r - 1) + 2;
    if (tmp > ret) ret = tmp;
  }
  tmp = solve(l + 1, r);
  if (tmp > ret) ret = tmp;
  tmp = solve(l, r - 1);
  if (tmp > ret) ret = tmp;
  return ret;
}
string ans = "";
void build(int l, int r) {
  if (l > r) {
    return;
  }
  if (l == r) {
    ans += str[l];
    return;
  }
  int tmp;
  if (str[l] == str[r]) {
    tmp = solve(l + 1, r - 1) + 2;
    if (solve(l, r) == tmp) {
      ans += str[l];
      build(l + 1, r - 1);
      return;
    }
  }
  tmp = solve(l + 1, r);
  if (tmp == solve(l, r)) {
    build(l + 1, r);
    return;
  }
  tmp = solve(l, r - 1);
  if (tmp == solve(l, r)) {
    build(l, r - 1);
    return;
  }
  return;
}
int main() {
  scanf("%s", str);
  for (int i = 0; str[i]; i++) {
    cnt[str[i] - 'a']++;
  }
  for (int i = 0; i < 26; i++) {
    if (cnt[i] >= 100) {
      int tmp = 100;
      while (tmp--) printf("%c", (char)(i + 'a'));
      puts("");
      exit(0);
    }
  }
  len = strlen(str);
  memset(memo, -1, sizeof memo);
  int res = solve(0, len - 1);
  if (res <= 100) {
    if (res & 1) res--;
    res /= 2;
    res--;
    build(0, len - 1);
    while (res >= 0) {
      ans += ans[res];
      res--;
    }
  } else {
    build(0, len - 1);
    string tmp = "";
    for (int i = 0; i < 50; i++) tmp += ans[i];
    for (int i = 49; i >= 0; i--) tmp += ans[i];
    ans = tmp;
  }
  cout << ans << endl;
}