Palindrome

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·10⁴) 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:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <memory.h>

using namespace std;

const int N = 55555;
const int R = 50;

char s[N];
int f[N][R + 10], p[N][R + 10];
int last[33];
int prev[N][33];
bool mark[N];

int main() {
scanf("%s", s);
int n = strlen(s);
for (int i=0;i<n;i++) s[i] -= 'a';
  for (int j=0;j<26;j++) last[j] = -1;
  for (int i=0;i<=n;i++) {
    for (int j=0;j<26;j++) prev[i][j] = last[j];
    last[s[i]] = i;
  }
  for (int i=0;i<=n;i++)
    for (int j=0;j<=R;j++) f[i][j] = -1, p[i][j] = 0;
  f[0][0] = n;
  for (int i=0;i<n;i++)
    for (int j=0;j<=R;j++) {
      if (f[i][j] == -1) continue;
      if (f[i][j] > f[i+1][j]) {
f[i+1][j] = f[i][j];
p[i+1][j] = 0;
}
int ft = prev[f[i][j]][s[i]];
if (ft > f[i+1][j+1]) {
f[i+1][j+1] = ft;
p[i+1][j+1] = 1;
}
}
int mx = 0, mi = -1, mj = -1;
for (int i=1;i<=n;i++)
    for (int j=1;j<=R;j++)
      if (f[i][j] >= i - 1) {
int len = 2 * j;
if (f[i][j] == i - 1) len--;
if (len > mx) {
mx = len;
mi = i;
mj = j;
}
}
for (int i=0;i<n;i++) mark[i] = false;
  int j = mj;
  for (int i=mi;i>0;i--)
if (p[i][j] == 1) {
mark[i - 1] = true;
mark[f[i][j]] = true;
j--;
}
for (int i=0;i<n;i++)
    if (mark[i]) putchar(s[i] + 'a');
  putchar('\n');
  return 0;
}