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 long long int inf = 1000000000;
const long long int mod = 1000000000 + 7;
inline void IO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline int dcmp(long double x) { return x < -1e-12 ? -1 : (x > 1e-12); }
template <class T>
inline int CHECK(T MASK, int i) {
  return (MASK >> i) & 1;
}
template <class T>
inline T ON(T MASK, int i) {
  return MASK | (T(1) << i);
}
template <class T>
inline T OFF(T MASK, int i) {
  return MASK & (~(T(1) << i));
}
template <typename T>
inline int CNT(T MASK) {
  if (numeric_limits<T>::digits <= numeric_limits<unsigned int>::digits)
    return __builtin_popcount(MASK);
  else
    return __builtin_popcountll(MASK);
}
template <class T>
inline int RIGHT(T MASK) {
  return log2(MASK & -MASK);
}
int dx4[] = {0, 0, -1, +1};
int dy4[] = {+1, -1, 0, 0};
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
inline void I(int& a) { scanf("%d", &a); }
inline void I(long long int& a) { scanf("%I64d", &a); }
inline void I(unsigned long long int& a) { scanf("%I64u", &a); }
inline void I(char* a) { scanf("%s", a); }
char Iarr[2000010];
inline void I(string& a) {
  scanf("%s", Iarr);
  a = Iarr;
}
template <typename T, typename... Args>
void I(T& a, Args&... args) {
  I(a);
  I(args...);
}
inline void OUT(int a) { printf("%d", a); }
inline void OUT(long long int a) { printf("%I64d", a); }
inline void OUT(const char* a) { printf("%s", a); }
inline void OUT(char* a) { printf("%s", a); }
inline void OUT(bool a) { printf("%d", a); }
inline void OUT(string a) {
  for (__typeof(a.end()) it = (a.begin()) - ((a.begin()) > (a.end()));
       it != (a.end()) - ((a.begin()) > (a.end()));
       it += 1 - 2 * ((a.begin()) > (a.end())))
    printf("%c", *it);
}
inline void OUT(unsigned long long int a) { printf("%I64u", a); }
template <typename T, typename... Args>
void OUT(T a, Args... args) {
  OUT(a);
  OUT(" ");
  OUT(args...);
}
template <typename... Args>
void O(Args... args) {
  OUT(args...);
  OUT("\n");
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << "{" << p.first << ", " << p.second << "}";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& a) {
  os << "[";
  for (int i = 0; i < (int)a.size(); i++) {
    if (i) os << ", ";
    os << a[i];
  }
  os << "]";
  return os;
}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cout << *it << " = " << a << endl;
  err(++it, args...);
}
const int M = 50010;
int pre[M][26];
int query(int in, char c) { return pre[in][c - 'a']; }
int main() {
  string s;
  I(s);
  for (int i = 0; i < (int)s.size(); i++) {
    for (int j = 0; j < 26; j++) {
      if (i)
        pre[i][j] = pre[i - 1][j];
      else
        pre[i][j] = -1;
    }
    pre[i][s[i] - 'a'] = i;
  }
  int dp[(int)s.size()][101];
  for (int i = 0; i < (int)s.size(); i++) {
    for (int j = 1; j <= 100; j++) {
      dp[i][j] = -1;
      if (j == 1)
        dp[i][j] = i;
      else if (i) {
        dp[i][j] = dp[i - 1][j];
        int in;
        if (j != 2)
          in = dp[i - 1][j - 2];
        else
          in = i;
        if (in > 0) {
          int q = query(in - 1, s[i]);
          if (q != -1) {
            dp[i][j] = max(dp[i][j], q);
          }
        }
      }
    }
  }
  int len, st;
  for (int i = 100; i >= 1; i--) {
    if (dp[(int)s.size() - 1][i] != -1) {
      len = i;
      st = dp[(int)s.size() - 1][i];
      break;
    }
  }
  string second;
  second.resize(len);
  for (int i = (int)s.size() - 1; i >= 0 && len > 0; i--) {
    if (s[st] == s[i]) {
      int u = ((int)second.size() - len) / 2;
      second[u] = s[st];
      second[u + len - 1] = s[st];
      len -= 2;
      if (len > 0 && i) st = dp[i - 1][len];
    }
  }
  O(second);
  return 0;
}