#include<cstring>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
bool ISpal(string s)
{
string t = s;
reverse(t.begin(), t.end());
return t == s;
}
string preProcess(string s) {
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
int n = T.length();
int *P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] >= maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
delete[] P;
return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
}
char s[100001];
int main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
while (cin >> s)
{
string os(s);
if (!ISpal(os))
{
int cen = os.length() - 1;
string pal = longestPalindrome(os);
int l = pal.length();
int f = os.find(pal);
string b_pal = os.substr(0, f);//before pal
string a_pal = os.substr(f + l);//after pal
reverse(b_pal.begin(), b_pal.end());
if (a_pal != "")
{
int pos = 1;
reverse(a_pal.begin(), a_pal.end());
while (pos <= a_pal.length() && ISpal(a_pal.substr(0, pos * 2 + 1)))
pos++;
a_pal.erase(0, pos);
os += a_pal + pal + b_pal;
while (os[cen] == os[cen + 1])
os.erase(cen + 1, 1);
}
else
{
os += b_pal;
}
}
cout << os << endl;
//puts(&os[0]);
}
return 0;
}
I2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxzdHJpbmc+CiNpbmNsdWRlPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgpib29sIElTcGFsKHN0cmluZyBzKQp7CglzdHJpbmcgdCA9IHM7CglyZXZlcnNlKHQuYmVnaW4oKSwgdC5lbmQoKSk7CglyZXR1cm4gdCA9PSBzOwp9CgpzdHJpbmcgcHJlUHJvY2VzcyhzdHJpbmcgcykgewoJaW50IG4gPSBzLmxlbmd0aCgpOwoJaWYgKG4gPT0gMCkgcmV0dXJuICJeJCI7CglzdHJpbmcgcmV0ID0gIl4iOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJcmV0ICs9ICIjIiArIHMuc3Vic3RyKGksIDEpOwoKCXJldCArPSAiIyQiOwoJcmV0dXJuIHJldDsKfQoKc3RyaW5nIGxvbmdlc3RQYWxpbmRyb21lKHN0cmluZyBzKSB7CglzdHJpbmcgVCA9IHByZVByb2Nlc3Mocyk7CglpbnQgbiA9IFQubGVuZ3RoKCk7CglpbnQgKlAgPSBuZXcgaW50W25dOwoJaW50IEMgPSAwLCBSID0gMDsKCWZvciAoaW50IGkgPSAxOyBpIDwgbiAtIDE7IGkrKykgewoJCWludCBpX21pcnJvciA9IDIgKiBDIC0gaTsgLy8gZXF1YWxzIHRvIGknID0gQyAtIChpLUMpCgoJCVBbaV0gPSAoUiA+IGkpID8gbWluKFIgLSBpLCBQW2lfbWlycm9yXSkgOiAwOwoKCQkvLyBBdHRlbXB0IHRvIGV4cGFuZCBwYWxpbmRyb21lIGNlbnRlcmVkIGF0IGkKCQl3aGlsZSAoVFtpICsgMSArIFBbaV1dID09IFRbaSAtIDEgLSBQW2ldXSkKCQkJUFtpXSsrOwoKCQkvLyBJZiBwYWxpbmRyb21lIGNlbnRlcmVkIGF0IGkgZXhwYW5kIHBhc3QgUiwKCQkvLyBhZGp1c3QgY2VudGVyIGJhc2VkIG9uIGV4cGFuZGVkIHBhbGluZHJvbWUuCgkJaWYgKGkgKyBQW2ldID4gUikgewoJCQlDID0gaTsKCQkJUiA9IGkgKyBQW2ldOwoJCX0KCX0KCgkvLyBGaW5kIHRoZSBtYXhpbXVtIGVsZW1lbnQgaW4gUC4KCWludCBtYXhMZW4gPSAwOwoJaW50IGNlbnRlckluZGV4ID0gMDsKCWZvciAoaW50IGkgPSAxOyBpIDwgbiAtIDE7IGkrKykgewoJCWlmIChQW2ldID49IG1heExlbikgewoJCQltYXhMZW4gPSBQW2ldOwoJCQljZW50ZXJJbmRleCA9IGk7CgkJfQoJfQoKCWRlbGV0ZVtdIFA7CgoJcmV0dXJuIHMuc3Vic3RyKChjZW50ZXJJbmRleCAtIDEgLSBtYXhMZW4pIC8gMiwgbWF4TGVuKTsKfQoKY2hhciBzWzEwMDAwMV07CmludCBtYWluKCkKewovLwlmcmVvcGVuKCJpbi5pbiIsICJyIiwgc3RkaW4pOwovLwlmcmVvcGVuKCJvdXQub3V0IiwgInciLCBzdGRvdXQpOwoJd2hpbGUgKGNpbiA+PiBzKQoJewoJCXN0cmluZyBvcyhzKTsKCQlpZiAoIUlTcGFsKG9zKSkKCQl7CgkJCWludCBjZW4gPSBvcy5sZW5ndGgoKSAtIDE7CgkJCXN0cmluZyBwYWwgPSBsb25nZXN0UGFsaW5kcm9tZShvcyk7CgkJCWludCBsID0gcGFsLmxlbmd0aCgpOwoJCQlpbnQgZiA9IG9zLmZpbmQocGFsKTsKCQkJc3RyaW5nIGJfcGFsID0gb3Muc3Vic3RyKDAsIGYpOy8vYmVmb3JlIHBhbAoJCQlzdHJpbmcgYV9wYWwgPSBvcy5zdWJzdHIoZiArIGwpOy8vYWZ0ZXIgcGFsCgkJCXJldmVyc2UoYl9wYWwuYmVnaW4oKSwgYl9wYWwuZW5kKCkpOwoJCQlpZiAoYV9wYWwgIT0gIiIpCgkJCXsJCQkJCgkJCQlpbnQgcG9zID0gMTsKCQkJCXJldmVyc2UoYV9wYWwuYmVnaW4oKSwgYV9wYWwuZW5kKCkpOwoJCQkJd2hpbGUgKHBvcyA8PSBhX3BhbC5sZW5ndGgoKSAmJiBJU3BhbChhX3BhbC5zdWJzdHIoMCwgcG9zICogMiArIDEpKSkKCQkJCQlwb3MrKzsKCQkJCWFfcGFsLmVyYXNlKDAsIHBvcyk7CQkJCQkJCQkKCQkJCW9zICs9IGFfcGFsICsgcGFsICsgYl9wYWw7CgkJCQl3aGlsZSAob3NbY2VuXSA9PSBvc1tjZW4gKyAxXSkKCQkJCQlvcy5lcmFzZShjZW4gKyAxLCAxKTsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCW9zICs9IGJfcGFsOwoJCQl9CQkJCQoJCX0KCQljb3V0IDw8IG9zIDw8IGVuZGw7CgkJLy9wdXRzKCZvc1swXSk7Cgl9CglyZXR1cm4gMDsKfQ==
YmNhZApiY2ViY2NhZWRiYWJjYmJkCmVjYWNkY2FlCmNkZQpkYmJjZWRiZQpjZGVhYQpiYmFiZGNhYmJhYWVjYgpiZWRjZWEKYWVjCmVkYWNkYmRkZWRiZWVjYQpkZWNiYmVlYWFlZGNiY2NjYwpiYmFiYmFlZWVhZWJjCmJiYWVjY2JjZGJhYmRlZWRiYwpkZWFkZGFhZWJkCmFiYmJhZWRlZGJhZGFlZWVlY2IKYmNhZQpjYmNkYWNlYmRhZWNhZGRkZApkZWJlZGRkZGJhZWQKZGVjY2JlZGFkCmVjYWVhYWVlYmVjCmVjYwplZGJjZGVkYmRhY2JhYWJiCmRhYWJlYmNhZGJjCmVjY2VhYmNlZWFkYmRiYmFkZWEKZWJlYgpkZGRhYWJiZWFhZWJjYmNhYmVkYwpkY2VlYmFjY2JiZGNiCmVlYmVlYmFjYWRjYWVkYWUKZWJiCmVjY2NhYWFjZWFjCmRkYWVhZWJlYmNhZWVlZWRiYWEKYwplZGFiY2VkYmViZWVjY2JlYmNkZApjZGRkYmRkZGRkCmRhZWNiZGVhYmRjZWFkCmRjZGNiYWNiYWRjZWJhCmJhZWRjYWRiY2VjZWRlYwpkYWJjZGViYWUKY2FjZWVlZWFlZGFjYWRiZWVjZGMKZGVlYWNhYmViY2JjYWNkYgplYQpiY2NlYWIKY2VkYWQKYmFiYmViY2RlYmFjYQphYmRjY2NiZWFjYWMKYWVlZWFiYWRjZGRiYWViY2JhZWMKZWNkYWRkCmRjZWRjZGNlYmVhZWRkYWRlZGMKZGQKZWNlZWRjZWRjYmMKYWNiCmFiY2ViY2JiYmNhZWFkYWJiYgpiZWIKZGFkYmEKY2VjCmJlYmRjZQplZWJjYWJhZGFkZWViYWViYWEKZWRkZGFjY2NjYWRlYmRiCmRlZWRlY2NhZGVhY2VjCmFjYmRkZGQKYmFkY2JkCmFkYWViYmRhZWRlYmFhZGQKYmFlZWFjCmRjYmJhYWIKYWRiY2NiZWJhZWNjZWFkYwphZGNhYWRlZWNjZWNhY2VlZGRiCmQKY2NkYmRkZWNjZWFiY2FjYmJlZGIKZGRjZQpiY2FlZGVkYmIKYWNiZWViYWJlZWVhZGVkYmVkZQpjY2RjYmNjCmFhCmFlYWJkY2ViYmRhZGNiY2FiYWVjCmJjY2ViYmFjZGFlY2MKYmVjZQpjY2JiZGFjYgpiYWFhZGUKYmFjYWRlYWFiYWRkY2RjYmEKZGFhYWNkZGNkYWNjY2JlYgplYWRlZGRhZGNhYmUKYmNjZWNiY2NiYWRkZQpiYWJkZWRkZGRjYWNlYWFhCmRjY2NiZGVlZWJlYWNlYmNjYgpjYWNjZWNlZGFiYmVhZGJjYwplZGJhY2JhYmFjYWJlY2JkYmMKYgpjZWVjZWVhZWJjZGViYWJlYWVlCmViYmRlZQpjYmRhZWViZGVhZGFjZGRkCmFhZGRiYWRkYmIKY2FhYmJhZGFhZWFlY2VlZWVlZQpiYmRlZGRlYmJhYmJjY2NlY2RiCmVjZApkY2NjZGNjYWRjYmRiZGJlYQphZGFhZWVkYWNlZWFiYwphYmRlYWRkZGNkYgphYWFkYmRhYmNlYgpkCmVlZGViZWNlYWRhZGRjZWU=
bcad
bcebccaedbabcbbd
ecacdcae
cde
dbbcedbe
cdeaa
bbabdcabbaaecb
bedcea
aec
edacdbddedbeeca
decbbeeaaedcbcccc
bbabbaeeeaebc
bbaeccbcdbabdeedbc
deaddaaebd
abbbaededbadaeeeecb
bcae
cbcdacebdaecadddd
debeddddbaed
deccbedad
ecaeaaeebec
ecc
edbcdedbdacbaabb
daabebcadbc
ecceabceeadbdbbadea
ebeb
dddaabbeaaebcbcabedc
dceebaccbbdcb
eebeebacadcaedae
ebb
ecccaaaceac
ddaeaebebcaeeeedbaa
c
edabcedbebeeccbebcdd
cdddbddddd
daecbdeabdcead
dcdcbacbadceba
baedcadbcecedec
dabcdebae
caceeeeaedacadbeecdc
deeacabebcbcacdb
ea
bcceab
cedad
babbebcdebaca
abdcccbeacac
aeeeabadcddbaebcbaec
ecdadd
dcedcdcebeaeddadedc
dd
eceedcedcbc
acb
abcebcbbbcaeadabbb
beb
dadba
cec
bebdce
eebcabadadeebaebaa
edddaccccadebdb
deedeccadeacec
acbdddd
badcbd
adaebbdaedebaadd
baeeac
dcbbaab
adbccbebaecceadc
adcaadeeccecaceeddb
d
ccdbddecceabcacbbedb
ddce
bcaededbb
acbeebabeeeadedbede
ccdcbcc
aa
aeabdcebbdadcbcabaec
bccebbacdaecc
bece
ccbbdacb
baaade
bacadeaabaddcdcba
daaacddcdacccbeb
eadeddadcabe
bccecbccbadde
babdeddddcaceaaa
dcccbdeeebeacebccb
caccecedabbeadbcc
edbacbabacabecbdbc
b
ceeceeaebcdebabeaee
ebbdee
cbdaeebdeadacddd
aaddbaddbb
caabbadaaeaeceeeeee
bbdeddebbabbcccecdb
ecd
dcccdccadcbdbdbea
adaaeedaceeabc
abdeadddcdb
aaadbdabceb
d
eedebeceadaddcee