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 MN = 2600 + 10;
int dp[MN][MN];
int go(string &line, int i, int j) {
  if (i > j) return 0;
  if (i == j) return 1;
  if (dp[i][j] != -1) return dp[i][j];
  int best = max(go(line, i + 1, j), go(line, i, j - 1));
  if (line[i] == line[j]) best = max(best, go(line, i + 1, j - 1) + 2);
  return dp[i][j] = best;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string line;
  while (cin >> line) {
    if (line.size() > 2600) {
      vector<int> frec(26);
      for (auto &i : line) frec[i - 'a']++;
      for (int i = 0; i < 26; ++i) {
        if (frec[i] > 100) {
          cout << string(100, i + 'a') << '\n';
          break;
        }
      }
    } else {
      memset(dp, -1, sizeof dp);
      int tar = min(go(line, 0, line.size() - 1), 100);
      int i = 0, j = line.size() - 1, l = 0, r = tar - 1;
      string ans(tar, 'a');
      while (i <= j && tar > 0) {
        if (tar == 1) {
          assert(i <= j);
          ans[l++] = line[i];
          break;
        }
        if (line[i] == line[j]) {
          ans[l++] = line[i];
          ans[r--] = line[j];
          i++;
          j--;
          tar -= 2;
          continue;
        }
        if (dp[i][j] == dp[i + 1][j])
          i++;
        else
          j--;
      }
      cout << ans << '\n';
    }
  }
  return 0;
}