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;
int dp[3000][3000];
int find_palindrome(char s[], int i, int j) {
  if (dp[i][j] >= 0) return dp[i][j];
  if (s[i] == s[j]) return dp[i][j] = 2 + find_palindrome(s, i + 1, j - 1);
  int a = find_palindrome(s, i + 1, j);
  int b = find_palindrome(s, i, j - 1);
  if (a > b)
    return dp[i][j] = a;
  else
    return dp[i][j] = b;
}
void printLongestPalindrome(char s[], int i, int j) {
  char answer[2605];
  int idx = 0;
  int flag = 0;
  while (i <= j) {
    if (s[i] == s[j]) {
      answer[idx++] = s[i];
      if (i == j) flag = 1;
      i++;
      j--;
    } else {
      if (dp[i + 1][j] > dp[i][j - 1])
        i++;
      else
        j--;
    }
  }
  for (int i = idx - flag - 1; i >= 0; i--) answer[idx++] = answer[i];
  answer[idx] = '\0';
  if (idx <= 100)
    cout << answer << endl;
  else {
    for (int index = 0; index < 50; index++) cout << answer[index];
    for (int index = idx - 50; index < idx; index++) cout << answer[index];
  }
}
void printP(char s[], int n) {
  int chars[26];
  for (int i = 0; i < 26; i++) chars[i] = 0;
  for (int i = 0; i < n; i++) chars[s[i] - 'a']++;
  for (int i = 0; i < 26; i++)
    if (chars[i] >= 100) {
      for (int j = 0; j < 100; j++) cout << (char)('a' + i);
      cout << endl;
      return;
    }
}
int main() {
  char s[50009];
  cin >> s;
  int n = strlen(s);
  if (n >= 2600) {
    printP(s, n);
    return 0;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (i == j)
        dp[i][j] = 1;
      else if (j < i)
        dp[i][j] = 0;
      else
        dp[i][j] = -1;
    }
  find_palindrome(s, 0, n - 1);
  int flag = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (dp[i][j] == -1) {
        find_palindrome(s, i, j);
      }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (dp[i][j] == 100) {
        flag = 1;
        printLongestPalindrome(s, i, j);
        return 0;
      }
  printLongestPalindrome(s, 0, n - 1);
  return 0;
}