#include #include #include #include class SuffixDataStructure { public: // a[i]>=0 SuffixDataStructure(const std::vector &a) : a(a) { sa = sufarray(a); buildLcp(); buildRmq(); } int getLcp(int i, int j) { if (i == j) { return a.size() - std::max(i, j); } i = isa[i]; j = isa[j]; if (i > j) { std::swap(i, j); } int k = lg[j - i]; return std::min(rmq[k][i], rmq[k][j - (1 << k)]); } private: const std::vector &a; std::vector sa; std::vector isa; std::vector lcp; std::vector lg; std::vector> rmq; std::vector sufarray(std::vector a) { const int TYPE_S = -1; const int TYPE_L = -2; const int n = a.size(); if (n == 1) { return std::vector(1); } std::vector type(n); type.back() = TYPE_S; for (int i = n - 2; i >= 0; i--) { if (a[i] < a[i + 1]) { type[i] = TYPE_S; } else if (a[i] > a[i + 1]) { type[i] = TYPE_L; } else { type[i] = type[i + 1]; } } std::vector lmsID; std::vector> lms; int prev = n; for (int i = n - 1; i >= 1; i--) { if (type[i - 1] == TYPE_L && type[i] == TYPE_S) { type[i] = lmsID.size(); lmsID.push_back(i); lms.emplace_back(std::vector(a.begin() + i, a.begin() + prev)); prev = i; } } auto inducedSort = [&](const std::vector &a, const std::vector &ordSS, const std::vector &type) { const int n = a.size(); const int maxi = *std::max_element(a.begin(), a.end()); std::vector sa(n, -1), L(maxi + 2), S(maxi + 2); for (int i = 0; i < n; i++) { L[a[i] + 1]++; } for (int i = 0; i < L.size() - 1; i++) { L[i + 1] += L[i]; S[i] = L[i + 1]; } for (int i = ordSS.size() - 1; i >= 0; i--) { int j = ordSS[i]; sa[--S[a[j]]] = j; } for (int i = 0; i < L.size() - 1; i++) { S[i] = L[i + 1]; } for (int i = 0; i < n; i++) { const int j = sa[i] - 1; if (j >= 0 && type[j] == TYPE_L) { sa[L[a[j]]++] = j; } } for (int i = n - 1; i >= 0; i--) { const int j = sa[i] - 1; if (j >= 0 && (type[j] == TYPE_S || type[j] >= 0)) { sa[--S[a[j]]] = j; } } return sa; }; const int SS = lmsID.size(); std::vector ordLms; for (int i : inducedSort(a, lmsID, type)) { if (type[i] >= 0) { ordLms.push_back(i); } } std::reverse(lmsID.begin(), lmsID.end()); std::vector rankLms(SS); for (int i = 1; i < SS; i++) { const int x = type[ordLms[i - 1]]; const int y = type[ordLms[i]]; rankLms[i] = rankLms[i - 1] + (lms[x] < lms[y]); } for (int i = 0; i < SS; i++) { type[ordLms[i]] = rankLms[i]; } std::vector lmsA; for (int i : lmsID) { lmsA.push_back(type[i]); } std::vector ordSS; for (int i : sufarray(lmsA)) { ordSS.push_back(lmsID[i]); } return inducedSort(a, ordSS, type); } void buildLcp() { const int n = a.size() - 1; isa.resize(n + 1); lcp.assign(n + 1, 0); for (int i = 0; i <= n; i++) { isa[sa[i]] = i; } int k = 0; for (int i = 0; i < n; i++) { int j = sa[isa[i] - 1]; k = std::max(0, k - 1); while (i + k < n && j + k < n && a[i + k] == a[j + k]) { k++; } lcp[isa[i] - 1] = k; } } void buildRmq() { const int n = lcp.size(); lg.resize(n + 1); for (int i = 2; i <= n; i++) { lg[i] = lg[i / 2] + 1; } const int m = lg[n]; rmq.assign(m + 1, std::vector(n)); for (int i = 0; i < n; i++) { rmq[0][i] = lcp[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j + (1 << i) < n; j++) { rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]); } } } }; int main() { int n; std::cin >> n; std::vector start(n); std::vector len(n); std::vector t; for (int i = 0; i < n; i++) { start[i] = t.size(); static char buf[100001]; scanf("%s", buf); int j; for (j = 0; buf[j] != 0; j++) { t.push_back(buf[j]); } len[i] = j; } t.push_back(0); SuffixDataStructure suf(t); int m, x, d; std::cin >> m >> x >> d; long long ans = 0; for (int k = 0; k < m; k++) { int i = (x / (n - 1)) + 1; int j = (x % (n - 1)) + 1; if (i > j) { std::swap(i, j); } else { j = j + 1; } x = (x + d) % (1LL * n * (n - 1)); i--; j--; ans += std::min(suf.getLcp(start[i], start[j]), std::min(len[i], len[j])); } std::cout << ans << std::endl; }