#include <iostream>
#include <cassert>
#include <algorithm>
#include <array>
#include <string>
#include <unordered_map>
#include <chrono>
// S('t' "alpha" 'h')
std::string palindrome(const std::string& s) {
// so slow ... trying to search in cache
static std::unordered_map<std::string, std::string> cache;
if (cache.find(s) != end(cache)) {
return cache[s];
}
//////////////////////////////////////////
if (s.size() == 0 || s.size() == 1) {
return s;
}
std::string alpha{ s.substr(1, s.size() - 2) };
if (s.front() == s.back()) {
std::string result = s.front() + palindrome(alpha) + s.back();
cache[s] = result;
return result;
}
std::array<std::string, 3> branches;
// S(alpha t)
std::string alpha_t{ s.substr(1) };
branches[0] = palindrome(alpha_t);
if (branches[0].size() == alpha_t.size()) {
cache[s] = branches[0];
return branches[0];
}
// S(h alpha)
std::string h_alpha{ s.substr(0, s.size() - 1) };
branches[1] = palindrome(h_alpha);
if (branches[1].size() == h_alpha.size()) {
cache[s] = branches[1];
return branches[1];
}
// S(alpha)
branches[2] = palindrome(alpha);
auto result = std::max_element(branches.begin(), branches.end(), []
(const std::string& a, const std::string& b) {
return a.size() < b.size();
});
cache[s] = *result;
return *result;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::string str;
std::cin>>str;
std::cout<<palindrome(str);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGFycmF5PgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPGNocm9ubz4KIAovLyBTKCd0JyAiYWxwaGEiICdoJykKc3RkOjpzdHJpbmcgcGFsaW5kcm9tZShjb25zdCBzdGQ6OnN0cmluZyYgcykgewogICAgLy8gc28gc2xvdyAuLi4gdHJ5aW5nIHRvIHNlYXJjaCBpbiBjYWNoZQogICAgc3RhdGljIHN0ZDo6dW5vcmRlcmVkX21hcDxzdGQ6OnN0cmluZywgc3RkOjpzdHJpbmc+IGNhY2hlOwogICAgaWYgKGNhY2hlLmZpbmQocykgIT0gZW5kKGNhY2hlKSkgewogICAgICAgIHJldHVybiBjYWNoZVtzXTsKICAgIH0KICAgIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwogICAgaWYgKHMuc2l6ZSgpID09IDAgfHwgcy5zaXplKCkgPT0gMSkgewogICAgICAgIHJldHVybiBzOwogICAgfQogICAgc3RkOjpzdHJpbmcgYWxwaGF7IHMuc3Vic3RyKDEsIHMuc2l6ZSgpIC0gMikgfTsKICAgIGlmIChzLmZyb250KCkgPT0gcy5iYWNrKCkpIHsKICAgICAgICBzdGQ6OnN0cmluZyByZXN1bHQgPSBzLmZyb250KCkgKyBwYWxpbmRyb21lKGFscGhhKSArIHMuYmFjaygpOwogICAgICAgIGNhY2hlW3NdID0gcmVzdWx0OwogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CiAgICBzdGQ6OmFycmF5PHN0ZDo6c3RyaW5nLCAzPiBicmFuY2hlczsKICAgIC8vIFMoYWxwaGEgdCkKICAgIHN0ZDo6c3RyaW5nIGFscGhhX3R7IHMuc3Vic3RyKDEpIH07CiAgICBicmFuY2hlc1swXSA9IHBhbGluZHJvbWUoYWxwaGFfdCk7CiAgICBpZiAoYnJhbmNoZXNbMF0uc2l6ZSgpID09IGFscGhhX3Quc2l6ZSgpKSB7CiAgICAgICAgY2FjaGVbc10gPSBicmFuY2hlc1swXTsKICAgICAgICByZXR1cm4gYnJhbmNoZXNbMF07CiAgICB9CiAgICAvLyBTKGggYWxwaGEpCiAgICBzdGQ6OnN0cmluZyBoX2FscGhheyBzLnN1YnN0cigwLCBzLnNpemUoKSAtIDEpIH07CiAgICBicmFuY2hlc1sxXSA9IHBhbGluZHJvbWUoaF9hbHBoYSk7CiAgICBpZiAoYnJhbmNoZXNbMV0uc2l6ZSgpID09IGhfYWxwaGEuc2l6ZSgpKSB7CiAgICAgICAgY2FjaGVbc10gPSBicmFuY2hlc1sxXTsKICAgICAgICByZXR1cm4gYnJhbmNoZXNbMV07CiAgICB9CiAgICAvLyBTKGFscGhhKQogICAgYnJhbmNoZXNbMl0gPSBwYWxpbmRyb21lKGFscGhhKTsKIAogICAgYXV0byByZXN1bHQgPSBzdGQ6Om1heF9lbGVtZW50KGJyYW5jaGVzLmJlZ2luKCksIGJyYW5jaGVzLmVuZCgpLCBbXQogICAgKGNvbnN0IHN0ZDo6c3RyaW5nJiBhLCBjb25zdCBzdGQ6OnN0cmluZyYgYikgewogICAgICAgIHJldHVybiBhLnNpemUoKSA8IGIuc2l6ZSgpOwogICAgfSk7IAogICAgCiAgICBjYWNoZVtzXSA9ICpyZXN1bHQ7CiAgICByZXR1cm4gKnJlc3VsdDsKfQppbnQgbWFpbigpCnsKCXN0ZDo6aW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CglzdGQ6OnN0cmluZyBzdHI7CglzdGQ6OmNpbj4+c3RyOwoJc3RkOjpjb3V0PDxwYWxpbmRyb21lKHN0cik7Cn0=