Untitled

ll t[inf], p[inf], s[inf];
string a;
 
ll get_hash(int l, int r) {
    return (t[l] - t[r + 1] * p[r - l + 1] + m2) % mod;
}
 
string calc(string a) {
    int n = a.size();
    a = ' ' + a;
    s[0] = 0;
    FORD(i, 1, n) s[i] = (s[i - 1] * base + a[i]) % mod;
 
    t[n + 1] = 0;
    REPD(i, n, 1) t[i] = (t[i + 1] * base + a[i]) % mod;
 
    REPD(i, n, 1) {
        if (s[i] == get_hash(1, i)) {
            string suffix = a.substr(i + 1, n - i);
            reverse(All(suffix));
            return suffix + a.substr(1, n);
        }
    }
    return a;
}
 
void solve() {
    cin >> a;
    int n = a.size();
    p[0] = 1;
    FORD(i, 1, n) p[i] = (p[i - 1] * base) % mod;
 
    string s1 = calc(a);
    reverse(All(a));
    string s2 = calc(a);
 
    cout << ((s1.size() < s2.size()) ? s1 : s2) << el;
}