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 dx4[4] = {0, -1, 0, 1};
int dy4[4] = {1, 0, -1, 0};
int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Power(int base, int exp) {
  int ans = 1;
  while (exp > 0) {
    if (exp & 1) ans = (1LL * ans * base) % 1000000007;
    exp = exp >> 1;
    base = (1LL * base * base) % 1000000007;
  }
  return ans;
}
int nxt[26][50005] = {};
void input() {
  string s;
  cin >> s;
  int n = s.length();
  for (int i = 0; i < 26; i += 1) {
    nxt[i][n] = nxt[i][n - 1] = n;
    for (int j = n - 1 - 1; j >= 0; j -= 1) {
      if (s[j + 1] - 'a' == i)
        nxt[i][j] = j + 1;
      else
        nxt[i][j] = nxt[i][j + 1];
    }
  }
  int dp[n + 1][101];
  for (int i = 0; i < n + 1; i += 1) {
    for (int j = 0; j < 101; j += 1) dp[i][j] = n;
    dp[i][0] = i - 1;
    dp[i][1] = i;
  }
  for (int i = n - 1; i >= 0; i -= 1) {
    for (int j = 2; j < 101; j += 1)
      dp[i][j] = min(dp[i + 1][j], nxt[s[i] - 'a'][dp[i + 1][j - 2]]);
  }
  int j = 0;
  for (int j_ = 0; j_ < 101; j_ += 1)
    if (dp[0][j_] < n) j = j_;
  int i = 0;
  string s1 = "", s2 = "";
  while (j) {
    if (j == 1) {
      s1 += s[i];
      j--;
      break;
    }
    if (dp[i][j] == dp[i + 1][j])
      i++;
    else {
      s1 += s[i];
      s2 = s[i] + s2;
      i++;
      j -= 2;
    }
  }
  cout << s1 + s2 << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int q = 1;
  while (q--) input();
}