https://cses.fi/paste/d215266054eda1d466ea03/

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class CSESLongestPalidrome {
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
    static class Reader {
        private BufferedReader br;
        private String content;
        private StringTokenizer st;
 
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public boolean hasNext() throws IOException {
            if (st != null && st.hasMoreTokens()) return true;
 
            boolean next = (content = br.readLine()) != null && !content.isEmpty();
            if (next) st = new StringTokenizer(content);
            return next;
        }
 
        public String next() {
            try {
                hasNext();
            } catch (IOException e) {
            }
            return st.nextToken();
        }
    }
 
    static long MOD = (long) (1e9 + 7);
    static int N = (int) (1e7 + 7);
    static long x = 31;
    static long pw[] = new long[N]; // pw[i] = x^i % MDO
    static long ipw[] = new long[N]; // pw[i] = x^i % MDO
    static long v[] = new long[N];
 
    private static void make_hash(String s) { // s is 1-based
        int n = s.length();
 
        for (int i = 1; i < n; i++) {
            v[i] = (s.charAt(i) - 'a' + 1) * pw[i];
        }
        // prefix sum
        for (int i = 1; i < n; i++) {
            v[i] = (v[i - 1] + v[i]) % MOD;
        }
    }
 
    private static void build(String s) {
        pw[0] = 1;
        for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * x % MOD;
 
//        模逆元
//        ipw[0] = 1;
//        ipw[1] = pow(x, MOD - 2, MOD); // x^-1 = x 的 P-2 mod P
//                                       // 費馬小定理
//        for (int i = 1; i < N; i++) ipw[i] = ipw[i - 1] * ipw[1] % MOD;
 
        make_hash(s);
    }
 
    private static boolean query(int l, int r, int l1, int r1) {
//        long h1 = (v[r] - v[l - 1] + MOD) * ipw[l - 1] % MOD; // +MOD 可以確保結果是正數
//        long h2 = (v[r1] - v[l1 - 1] + MOD) * ipw[l1 - 1] % MOD;
        long h1 = (v[r] - v[l - 1] + MOD)% MOD;
        long h2 = (v[r1] - v[l1 - 1] + MOD)% MOD;
        
        return (h1 * pw[l1 - 1] % MOD) == (h2 * pw[l - 1] % MOD);
    }
    private static boolean isPal(int n, int l, int r) {
        // [l, r] is 1-base
        return query(l, r, 2 * n + 1 - r, 2 * n + 1 - l);
    }
 
    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        int max = 0;
 
        while (reader.hasNext()) {
            String s = reader.next();
            String tmp = " " + s + reverse(s);
            build(tmp);
 
            int n = s.length();
            int pos = -1;
            for (int i = 1; i <= n; i++) {
                 int l = 1;
                 int r = n;
                 while(l < r){
                     int mid = (l + r) >> 1;
                     if(!isValidPalLength(i, i + mid, n)){
                         r = mid;
                     }else{
                         l = mid + 1;
                     }
                 }
                 if(max < l){
                    max = l;
                    pos = i;
                 }
                
            }
            out.println(tmp.substring(pos, pos + max));
            out.flush();
        }
        
    }
    
    private static boolean isValidPalLength(int l, int r, int n ){
        if(l <= 0 || r > n){
            return false;
        }
        return  isPal(n, l, r) || isPal(n, l, r + 1) ;
    }
 
    private static String reverse(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return sb.toString();
    }
}

class Solution {
public:
int maximumScore(vector<int>& W, vector<vector<int>>& edges) {
int n = W.size();

using pii = pair<int, int>;
vector<vector<pii>> adj(n);
for (vector<int> edge: edges) {
int u = edge[0], v = edge[1];
adj[u].push_back({W[v], v});
adj[v].push_back({W[u], u});
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
reverse(adj[i].begin(), adj[i].end());
if (adj[i].size() > 3) adj[i].resize(3);
}

int ans = -1;
for (vector<int> edge: edges) {
int u = edge[0], v = edge[1];

for (auto [wx, x] : adj[u]) {
for (auto [wy, y] : adj[v]) {
if (x != y && y != u && x != v) {
int val = W[u]+W[v]+W[x]+W[y];
ans = max(ans, val);
}
}
}
}

return ans;
}
};