ChuoiDoiXung

#include <bits/stdc++.h>

using namespace std;

char a[2005], b[2005];
int f[2005][2005];

int main() {
    #ifndef ONLINE_JUDGE
        freopen("NKPALIN.inp", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%s", a);
    int len = strlen(a);
    for (int i=0; i<len; ++i) b[i] = a[i];
    reverse(b, b+len);
    memset(f, 0, sizeof f);

    for (int i=1; i<=len; ++i)
        for (int j=1; j<=len; ++j)
            if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1] + 1;
            else f[i][j] = max(f[i][j-1], f[i-1][j]);

    int i = len, j = len;
    vector <char> ans;
    while (i > 0 && j > 0)
    {
        if (a[i-1] == b[j-1])
        {
            ans.push_back(a[i-1]);
            --i; --j;
        }
        else
        {
            if (f[i][j] == f[i-1][j]) --i; else --j;
        }
    }

    //reverse(ans.begin(), ans.end());
    for (int i=0; i<ans.size(); ++i) cout << ans[i];

    return 0;
}