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;
typedef unsigned int T;
const int ALPHA_SIZE = 128;
const int W_LEN = sizeof(T) * 8;
const int SHIFT_LEN = (W_LEN == 32 ? 5 : 6);
const int MAX_N = 50000 + 10;
void LcsBit(int m, int n, const int* a, const int* b, int* res) {
  static T bit[ALPHA_SIZE][(MAX_N >> SHIFT_LEN) + 2];
  static T dp[(MAX_N >> SHIFT_LEN) + 2];
  int nbits = (m + W_LEN - 1) >> SHIFT_LEN;
  for (int i = 0; i < m; i++)
    bit[a[i]][i >> SHIFT_LEN] |= static_cast<T>(1) << (i & (W_LEN - 1));
  memset(dp, 0, nbits * sizeof(T));
  T top_bit, t, carry, x, y, *bit_s;
  for (int i = 0; i < n; i++) {
    top_bit = 1;
    bit_s = bit[b[i]];
    for (int j = carry = 0; j < nbits; j++) {
      x = dp[j] | bit_s[j];
      t = dp[j] >> (W_LEN - 1);
      y = (dp[j] << 1) | top_bit;
      top_bit = t;
      dp[j] = x & ((x - y - carry) ^ x);
      carry = (x < y + carry) ? 1 : 0;
    }
  }
  int sum = 0;
  for (int i = 0; i < m; i++) {
    if (dp[i >> SHIFT_LEN] & (static_cast<T>(1) << (i & (W_LEN - 1)))) ++sum;
    res[i] = sum;
    bit[a[i]][i >> SHIFT_LEN] = 0;
  }
}
int Lcs(int m, int n, const int* a, const int* b, int* c) {
  if (n <= 0 || m <= 0) {
    return 0;
  } else if (m == 1) {
    for (int i = 0; i < n; ++i) {
      if (a[0] == b[i]) {
        c[0] = a[0];
        return 1;
      }
    }
    return 0;
  }
  static int ra[MAX_N], rb[MAX_N];
  static int res1[MAX_N], res2[MAX_N];
  int i = (m - 1) >> 1;
  memcpy(ra, a, m * sizeof(int));
  memcpy(rb, b, n * sizeof(int));
  reverse(ra, ra + m);
  reverse(rb, rb + n);
  LcsBit(n, i + 1, b, a, res1);
  LcsBit(n, m - i - 1, rb, ra, res2);
  int len1 = 0, len2 = res2[n - 1], k = -1;
  for (int j = 0; j < n - 1; ++j) {
    if (res1[j] + res2[n - j - 2] > len1 + len2) {
      len1 = res1[j];
      len2 = res2[n - j - 2];
      k = j;
    }
  }
  if (res1[n - 1] > len1 + len2) {
    len1 = res1[n - 1];
    len2 = 0;
    k = n - 1;
  }
  if (len1 > 0) Lcs(i + 1, k + 1, a, b, c);
  if (len2 > 0) Lcs(m - i - 1, n - k - 1, a + i + 1, b + k + 1, c + k + 1);
  memmove(c + len1, c + k + 1, len2 * sizeof(int));
  return len1 + len2;
}
int a[MAX_N], b[MAX_N], c[MAX_N];
void Print(const int* s, int n) {
  if (n <= 100) {
    for (int i = 0; i < n; ++i) {
      printf("%c", s[i]);
    }
  } else {
    if (n % 2 == 0) {
      for (int i = (n - 100) / 2; i < (n - 100) / 2 + 100; ++i) {
        printf("%c", s[i]);
      }
    } else {
      for (int i = (n - 100) / 2; i < (n - 100) / 2 + 101; ++i) {
        if (i == (n / 2)) {
          continue;
        }
        printf("%c", s[i]);
      }
    }
  }
  printf("\n");
}
char s[MAX_N];
int main() {
  scanf("%s", s);
  int n = strlen(s);
  for (int i = 0; i < n; ++i) {
    a[i] = s[i];
  }
  reverse(s, s + n);
  for (int i = 0; i < n; ++i) {
    b[i] = s[i];
  }
  int clen = Lcs(n, n, a, b, c);
  Print(c, clen);
  return 0;
}