#include #include #include #include #include using namespace std; vector sufarray(vector a) { const int TYPE_S = -1; const int TYPE_L = -2; int n = a.size(); if (n == 1) { return vector(1); } 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]; } } vector lmsID; 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(vector(a.begin() + i, a.begin() + prev)); prev = i; } } auto inducedSort = [&](vector &a, vector &ordSS, vector &type) { int n = a.size(); vector sa(n, -1); int maxi = *max_element(a.begin(), a.end()); vector 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++) { 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--) { int j = sa[i] - 1; if (j >= 0 && (type[j] == TYPE_S || type[j] >= 0)) { sa[--S[a[j]]] = j; } } return sa; }; int SS = lmsID.size(); vector ordLms; for (int i : inducedSort(a, lmsID, type)) { if (type[i] >= 0) { ordLms.push_back(i); } } reverse(lmsID.begin(), lmsID.end()); vector rankLms(SS); for (int i = 1; i < SS; i++) { int x = type[ordLms[i - 1]]; 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]; } vector lmsA; for (int i : lmsID) { lmsA.push_back(type[i]); } vector ordSS; for (int i : sufarray(lmsA)) { ordSS.push_back(lmsID[i]); } return inducedSort(a, ordSS, type); } vector lcparray(const vector &s, const vector &sa) { const int n = s.size() - 1; vector isa(n + 1), lcp(n + 1); 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 = max(0, k - 1); while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++; lcp[isa[i] - 1] = k; } return lcp; } struct RMQ { vector lg; vector> dat; RMQ(const vector &a) { const int n = a.size(); lg.resize(n + 1); for (int i = 2; i <= n; i++) { lg[i] = lg[i / 2] + 1; } const int m = lg[n]; dat.assign(m + 1, vector(n)); for (int i = 0; i < n; i++) { dat[0][i] = a[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j + (1 << i) < n; j++) { dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]); } } } int getmin(int l, int r) { int k = lg[r - l]; return min(dat[k][l], dat[k][r - (1 << k)]); } }; int main() { int n; cin >> n; vector s(n); vector start(n); vector t; for (int i = 0; i < n; i++) { cin >> s[i]; start[i] = t.size(); for (char c : s[i]) { t.push_back(c); } t.push_back(i + 'z' + 1); } t.push_back(0); auto sa = sufarray(t); auto lcp = lcparray(t, sa); vector isa(t.size()); for (int i = 0; i < t.size(); i++) { isa[sa[i]] = i; } RMQ rmq(lcp); int m, x, d; 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) { swap(i, j); } else { j = j + 1; } x = (x + d) % (1LL * n * (n - 1)); i--; j--; if (isa[start[i]] > isa[start[j]]) { swap(i, j); } if (i == j) { ans += s[i].size(); } else { ans += rmq.getmin(isa[start[i]], isa[start[j]]); } } cout << ans << endl; }