#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define int long long #define double long double typedef vector VI; typedef pair pii; typedef vector VP; typedef vector VS; typedef priority_queue PQ; templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #define fore(i,a) for(auto &i:a) #define REP(i,n) for(int i=0;i, greater > q2; template struct SparseTable { vector > dat; vector height; SparseTable() { } SparseTable(const vector &vec) { init(vec); } void init(const vector &vec) { int n = (int)vec.size(), h = 0; while ((1 << h) < n) ++h; dat.assign(h, vector(1 << h)); height.assign(n + 1, 0); for (int i = 2; i <= n; i++) height[i] = height[i >> 1] + 1; for (int i = 0; i < n; ++i) dat[0][i] = vec[i]; for (int i = 1; i < h; ++i) for (int j = 0; j < n; ++j) dat[i][j] = min(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]); } MeetSemiLattice get(int a, int b) { return min(dat[height[b - a]][a], dat[height[b - a]][b - (1 << height[b - a])]); } }; // Suffix Array ( Manber&Myers: O(n (logn)^2) ) struct SuffixArray { string str; vector sa; // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n) vector lcp; // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1) inline int& operator [] (int i) { return sa[i]; } SuffixArray(const string& str_) : str(str_) { buildSA(); calcLCP(); } void init(const string& str_) { str = str_; buildSA(); calcLCP(); } // build SA vector rank_sa, tmp_rank_sa; struct CompareSA { int n, k; const vector &rank; CompareSA(int n, int k, const vector &rank_sa) : n(n), k(k), rank(rank_sa) {} bool operator()(int i, int j) { if (rank[i] != rank[j]) return (rank[i] < rank[j]); else { int rank_ik = (i + k <= n ? rank[i + k] : -1); int rank_jk = (j + k <= n ? rank[j + k] : -1); return (rank_ik < rank_jk); } } }; void buildSA() { int n = (int)str.size(); sa.resize(n + 1), lcp.resize(n + 1), rank_sa.resize(n + 1), tmp_rank_sa.resize(n + 1); for (int i = 0; i < n; ++i) sa[i] = i, rank_sa[i] = (int)str[i]; sa[n] = n, rank_sa[n] = -1; for (int k = 1; k <= n; k *= 2) { CompareSA csa(n, k, rank_sa); sort(sa.begin(), sa.end(), csa); tmp_rank_sa[sa[0]] = 0; for (int i = 1; i <= n; ++i) { tmp_rank_sa[sa[i]] = tmp_rank_sa[sa[i - 1]]; if (csa(sa[i - 1], sa[i])) ++tmp_rank_sa[sa[i]]; } for (int i = 0; i <= n; ++i) rank_sa[i] = tmp_rank_sa[i]; } } vector rsa; SparseTable st; void calcLCP() { int n = (int)str.size(); rsa.resize(n + 1); for (int i = 0; i <= n; ++i) rsa[sa[i]] = i; lcp.resize(n + 1); lcp[0] = 0; int cur = 0; for (int i = 0; i < n; ++i) { int pi = sa[rsa[i] - 1]; if (cur > 0) --cur; for (; pi + cur < n && i + cur < n; ++cur) { if (str[pi + cur] != str[i + cur]) break; } lcp[rsa[i] - 1] = cur; } st.init(lcp); } // calc lcp int getLCP(int a, int b) { // lcp of str.sutstr(a) and str.substr(b) return st.get(min(rsa[a], rsa[b]), max(rsa[a], rsa[b])); } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; string S = ""; VI A; int k = 0; A.push_back(0); REP(i, N) { string s; cin >> s; REP(j, s.size()) S.push_back(s[j]); k += s.size(); A.push_back(k); } SuffixArray T(S); int M, x, d; int ans = 0; cin >> M >> x >> d; VI I(M + 1), J(M + 1); eFOR(k, 1, M) { I[k] = (x / (N - 1)) + 1; J[k] = (x % (N - 1)) + 1; if (I[k] > J[k])swap(I[k], J[k]); else J[k] = J[k] + 1; x = (x + d) % (N * (N - 1)); } eFOR(k, 1, M) { int i = I[k], j = J[k]; //cout << i << " " << j << endl; i--, j--; //cout << i << " " << j << endl; ans += T.getLCP(A[i], A[j]); } cout << ans << endl; return 0; }