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 N = 10000, MS = 100;
short dp[N][N];
char s[N * 5 + 1];
int cnt[26];
inline short max(short a, short b) {
  if (a > b)
    return a;
  else
    return b;
}
short DPS(int l, int r) {
  if (l > r)
    return 0;
  else if (l == r) {
    return dp[l][r] = 1;
  } else if (dp[l][r] != 0) {
    return dp[l][r];
  } else {
    short tmp = 0, cnt1 = DPS(l + 1, r), cnt2 = DPS(l, r - 1),
          cnt0 = DPS(l + 1, r - 1) + ((s[l] == s[r]) ? 2 : 0);
    if (tmp < cnt1) {
      tmp = cnt1;
    }
    if (tmp < cnt2) {
      tmp = cnt2;
    }
    if (tmp < cnt0) {
      tmp = cnt0;
    }
    dp[l][r] = tmp;
    if (dp[l][r] > MS)
      return dp[l][r] = MS;
    else
      return dp[l][r];
  }
}
void DFS(int i, int j, short cnt) {
  if (i > j || cnt == 0) {
    return;
  } else if (i == j) {
    putchar(s[i]);
  } else if (s[i] == s[j] && cnt >= 2) {
    putchar(s[i]);
    DFS(i + 1, j - 1, cnt - 2);
    putchar(s[j]);
  } else if (dp[i + 1][j] >= cnt) {
    DFS(i + 1, j, cnt);
  } else {
    DFS(i, j - 1, cnt);
  }
}
int main() {
  memset(cnt, 0, sizeof(cnt));
  scanf("%s", s);
  int n = 0;
  while (s[n]) cnt[s[n++] - 'a']++;
  if (n >= 10000) {
    int i;
    for (i = 0; i < 26; i++) {
      if (cnt[i] >= MS) break;
    }
    memset(s, (char)(i + 'a'), MS * sizeof(char));
    s[MS] = '\0';
    puts(s);
  } else {
    memset(dp, 0, sizeof(dp));
    short ans = 0;
    int l = 0, r = 0;
    DPS(0, n - 1);
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        short tp = dp[i][j];
        if (ans < tp && tp <= MS) {
          ans = tp;
          l = i;
          r = j;
        }
      }
    }
    DFS(l, r, ans);
    puts("");
  }
  return 0;
}