#include <bits/stdc++.h> using namespace std; #define ULL unsigned long long #define P 131 const int N = 1e6 + 10; ULL h[N], p[N]; char s[2 * N]; char s1[N]; ULL h1[N], p1[N]; ULL get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } ULL get_hash_d(int l, int r) { return h1[r] - h1...