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 N = 50 * 1000 + 10;
int dp[N][110], ss;
pair<int, int> par[N][110];
vector<int> ch[40];
string s;
set<pair<int, char>> sv, ans;
void solve() {
  for (int i = 0; i < ss; i++) {
    dp[i][1] = i, ch[int(s[i] - 'a')].push_back(i);
    if (s[i] == s[i + 1]) dp[i][2] = i + 1;
  }
  for (int i = ss - 2; ~i; i--) {
    int pl = int(s[i] - 'a');
    for (int j = 1; j < 101; j++) {
      if (dp[i + 1][j]) {
        if (i == 0 && j == 1) continue;
        if (!dp[i][j])
          dp[i][j] = dp[i + 1][j], par[i][j] = par[i + 1][j];
        else if (dp[i + 1][j] < dp[i][j])
          dp[i][j] = dp[i + 1][j], par[i][j] = {i + 1, j};
      } else
        continue;
      int bs = upper_bound(ch[pl].begin(), ch[pl].end(), dp[i + 1][j]) -
               ch[pl].begin();
      if (bs < (int)ch[pl].size())
        dp[i][j + 2] = ch[pl][bs], par[i][j + 2] = {i + 1, j};
    }
    int bs = upper_bound(ch[pl].begin(), ch[pl].end(), i) - ch[pl].begin();
    if (bs < (int)ch[pl].size())
      dp[i][2] = (dp[i][2] ? min(dp[i][2], ch[pl][bs]) : ch[pl][bs]);
  }
}
void build_str() {
  int mx = 1, cnt = 0, ted = -1;
  for (int i = 1; i < 101; i++)
    if (dp[0][i]) mx = i;
  pair<int, int> tmp = {0, mx};
  while (tmp.second) {
    int x = par[tmp.first][tmp.second].first,
        y = par[tmp.first][tmp.second].second;
    if (tmp.second > 1)
      sv.insert({dp[tmp.first][tmp.second], s[dp[tmp.first][tmp.second]]});
    else
      ted = dp[tmp.first][tmp.second];
    tmp.first = x, tmp.second = y;
  }
  if (ted ^ -1) ans.insert({ted, s[ted]});
  for (auto [x, y] : sv) {
    if (ans.size() == 100) break;
    ans.insert({x, y}), ans.insert({-x, y});
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  cin >> s, ss = s.size();
  solve();
  build_str();
  for (auto [x, y] : ans) cout << y;
  cout << '\n';
}