#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(2, 1)); hash.assign(n+1, vector(2, 0)); for(int i=0; i getHash(int a, int b) const{ vector ans(2); for(int i=0; i<2; ++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_pair(ans[0], ans[1]); } }; 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(0, mid-1) != b.getHash(0, 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; map, int> memo; for(int i=0; i key(a[i], b[i]); if(memo.find(key) != memo.end()){ ans += memo[key]; } else{ int len = min(s[a[i]].size(), s[b[i]].size()); int tmp = solve(len, rh[a[i]], rh[b[i]]); ans += tmp; memo[key] = tmp; } } cout << ans << endl; return 0; }