#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class RollingHash { private: static const int X[], M[]; vector > xp; vector > hash; public: RollingHash(const string& s){ int n = s.size(); xp.assign(n+1, vector(3, 1)); hash.assign(n+1, vector(3, 0)); for(int i=0; i getHash(int a) const{ return make_tuple(hash[a+1][0], hash[a+1][1], hash[a+1][2]); } tuple getHash(int a, int b) const{ vector ans(3); for(int i=0; i<3; ++i){ ans[i] = hash[b+1][i]; ans[i] -= hash[a][i] * xp[b-a+1][i]; ans[i] %= M[i]; if(ans[i] < 0) ans[i] += M[i]; } return make_tuple(ans[0], ans[1], ans[2]); } }; const int RollingHash::X[] = {1685440109, 1389328937, 1813126193}; // 素数 const int RollingHash::M[] = {2000000087, 2000000089, 2000000099}; // 合同式の法(素数) int solve(int len, const RollingHash& a, const RollingHash& b) { int left = 0; int right = len; while(left < right){ int mid = (left + right + 1) / 2; if(a.getHash(mid-1) != b.getHash(mid-1)) right = mid - 1; else left = mid; } return left; } int main() { int n; cin >> n; vector s(n); for(int i=0; i> s[i]; vector rh; for(int i=0; i> m >> x >> d; vector a(m), b(m); for(int i=0; i b[i]) swap(a[i], b[i]); else ++ b[i]; x = (x + d) % (n * (n - 1LL)); } long long ans = 0; for(int i=0; i