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 LEN = 50001;
const int FREQ = 51;
const int SYM = 128;
char s[LEN];
int pr[SYM][LEN];
int sym[SYM][FREQ];
int from[SYM][FREQ];
int rev[SYM][FREQ];
int dp[LEN][FREQ];
int fromdp[LEN][FREQ];
int main() {
  scanf("%s", s);
  int len = (int)strlen(s);
  for (char i = 'a'; i <= 'z'; i++) {
    int cur = -1;
    for (int j = 0; j <= len; j++) {
      pr[i][j] = cur;
      if (s[j] == i) {
        cur = j;
      }
    }
  }
  for (char i = 'a'; i <= 'z'; i++) {
    for (int j = 0; j <= 50; j++) {
      sym[i][j] = -1;
    }
    sym[i][0] = len;
  }
  int maxlen = 0;
  int maxi = 0;
  int maxc = 0;
  char divc = -1;
  for (int i = 0; i < len; i++) {
    for (int j = 50; j > 0; j--) {
      dp[i][j] = -1;
      for (char c = 'a'; c <= 'z'; c++) {
        int cur = sym[c][j - 1];
        if (cur == -1) {
          continue;
        }
        int next = pr[s[i]][cur];
        if (next > i) {
          if (next > sym[s[i]][j]) {
            sym[s[i]][j] = next;
            from[s[i]][j] = c;
            rev[s[i]][j] = i;
          }
          if (next > dp[i][j]) {
            dp[i][j] = next;
            fromdp[i][j] = rev[c][j - 1];
          }
        }
      }
      if (i < dp[i][j]) {
        int len = 2 * j;
        char div = -1;
        if (i + 1 < dp[i][j] && len < 100) {
          len++;
          div = s[i + 1];
        }
        if (len > maxlen) {
          maxlen = len;
          maxi = i;
          maxc = j;
          divc = div;
        }
      }
    }
  }
  if (maxlen == 0) {
    printf("%c", s[0]);
    return 0;
  }
  vector<char> v;
  while (maxc > 0) {
    v.push_back(s[maxi]);
    maxi = fromdp[maxi][maxc];
    maxc--;
  }
  for (int j = (int)v.size() - 1; j >= 0; j--) {
    printf("%c", v[j]);
  }
  if (divc != -1) {
    printf("%c", divc);
  }
  for (int j = 0; j < v.size(); j++) {
    printf("%c", v[j]);
  }
}