Untitled

/// Manacher - O(N)

#include <bits/stdc++.h>
using namespace std;

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

// int main() {
//   string p = "abababc";
//   vector<int> manacher_ = manacher(p);
//   for(int v : manacher_) {
//     cout<<v<<' ';
//   }
//   cout<<'\n';
// }

int main() {
  string p; cin>>p;
  
  vector<int> manacher_ = manacher(p);

  int ma = 0, pos;
  for(int i = 0; i < (int)manacher_.size(); ++i) {
    const int v = manacher_[i];
    if(v > ma) {
      ma = v, pos = i - (i+1)/2;
    }
  }
  
  --ma;
  string ans = "";
  const int aux = ma / 2;
  for(int i = max(pos - aux, 0); i <= pos - 1; ++i) {
    ans += p[i];
  }
  
  ans += p[pos];
  for(int i = pos + 1; i <= min((int)p.size(), pos + aux); ++i) {
    ans += p[i];
  }
  
  const int sz = (int)ans.size();
  int i, j;
  for(i = 0, j = sz-1; ans[i] == ans[j] && i < j; ++i, --j);
  if(i < j) {
    for(i = 0, j = sz-2; ans[i] == ans[j] && i < j; ++i, --j);
    if(i >= j) {
      ans.pop_back();
      cout<<ans<<'\n';
    } else {
      for(int i = 1; i < sz; ++i) cout<<ans[i];
      cout<<'\n';
    }
  } else cout<<ans<<'\n';
}