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 ans, ans1, ans2, n, cou[1000], cur, dp[100000][200], Next[100000][100];
string s;
int main() {
  cin >> s;
  n = s.length();
  s = '0' + s;
  string s2;
  int cur;
  cin >> s2;
  cur = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == s2[cur]) {
      cur++;
    }
  }
  char c;
  if (s.size() >= 2600) {
    char c;
    for (int i = 0; i < s.size(); i++) {
      cou[s[i] - 'a']++;
      if (cou[s[i] - 'a'] == 100) {
        c = s[i];
        break;
      }
    }
    for (int i = 0; i < 100; i++) cout << c;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 100; j++) dp[i][j] = 0;
  }
  int tmp[100000];
  for (int i = 0; i <= 30; i++) tmp[i] = 0;
  for (int i = 0; i <= 30; i++) dp[0][i] = 0;
  for (int i = 0; i <= n; i++) dp[i][0] = n + 1;
  for (int i = 1; i <= n + 1; i++) {
    for (int j = 0; j <= 30; j++) Next[i][j] = tmp[j];
    if (i <= n) tmp[s[i] - 'a'] = i;
  }
  for (int l = 1; l <= 50; l++) {
    cur = 0;
    for (int i = 0; i <= n; i++) {
      cur = max(cur, dp[i][l - 1]);
      tmp[i] = cur;
    }
    for (int i = l; i <= n; i++) {
      if (Next[tmp[i - 1]][s[i] - 'a'] >= i)
        dp[i][l] = Next[tmp[i - 1]][s[i] - 'a'];
      if (ans < 2 * l - 1 && dp[i][l] == i && 2 * l - 1 <= 100) {
        ans1 = i;
        ans2 = l;
        ans = 2 * l - 1;
      }
      if (ans < 2 * l && dp[i][l] > i && 2 * l <= 100) {
        ans1 = i;
        ans2 = l;
        ans = 2 * l;
      }
    }
  }
  string ansstr = "", anstmp = "";
  for (int i = ans1; i >= 0; i--) {
    if (dp[i][ans2 - 1] > dp[ans1][ans2] && i < ans1) {
      ansstr = ansstr + s[ans1];
      if (ans % 2 > 0) {
        ans--;
      } else
        anstmp = s[ans1] + anstmp;
      ans1 = i;
      ans2--;
    }
    if (ans2 == 0) break;
  }
  cout << anstmp + ansstr;
}