#include using namespace std; using ll = long long; struct SuffixArray { string str; vector sa; SuffixArray() {} SuffixArray(const string& s) : str(s) { constructSA(); } // O(N (log N)^2) void constructSA() { if (str.empty()) return; int n = str.size(); sa.resize(n + 1); vector rank(n + 1); for (int i = 0; i <= n; i++) { sa[i] = i; rank[i] = (i < n ? str[i] : -1); } int len; auto compare_sa = [&](const int i, const int j) { if (rank[i] != rank[j]) return rank[i] < rank[j]; else { int ri = (i + len <= n ? rank[i + len] : -1); int rj = (j + len <= n ? rank[j + len] : -1); return ri < rj; } }; vector tmp(n + 1); for (len = 1; len <= n; len <<= 1) { sort(sa.begin(), sa.end(), compare_sa); tmp[sa[0]] = 0; for (int i = 1; i <= n; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for (int i = 0; i <= n; i++) { rank[i] = tmp[i]; } } } int operator[](int idx) const { return sa[idx]; } // 文字列s以上となる最小の接尾辞について、SAのindexを返す(無いならsa.size()を返す) int lower_bound(const string& s) { int ng = -1, ok = sa.size(); while (ok - ng > 1) { int mid = (ok + ng) >> 1; (str.compare(sa[mid], s.size(), s) < 0 ? ng : ok) = mid; } return ok; } // 文字列sが文字列strに含まれるならSAのindexを、無いなら-1を返す int find(const string& s) { int idx = lower_bound(s); return ((idx < sa.size() && str.compare(sa[idx], s.size(), s) == 0) ? idx : -1); } // 文字列sが文字列strに含まれるか? bool contain(const string& s) { return find(s) != -1; } }; template struct SparseTable { using T = typename SemiLattice::T; int n; vector< vector > table; vector log_table; SparseTable() {} SparseTable(const vector& v) { n = v.size(); log_table.resize(n + 1, 0); for (int i = 2; i <= n; i++) { log_table[i] = log_table[i >> 1] + 1; } table.resize(log_table[n] + 1, vector(n)); for (int i = 0; i < n; i++) { table[0][i] = v[i]; } size_t sz = table.size(); for (int i = 1; i < sz; i++) { for (int j = 0; j + (1 << i) <= n; j++) { table[i][j] = SemiLattice::merge(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } } } //区間[l, r)に対するクエリに答える T query(int l, int r) { assert(l < r); int k = log_table[r - l]; return SemiLattice::merge(table[k][l], table[k][r - (1 << k)]); } }; //以下、SemiLatticeの例 template struct RMQSL { using T = U; static T merge(T a, T b) { return min(a, b); } }; struct LongestCommonPrefixArray { vector lcp; const SuffixArray& sa; SparseTable< RMQSL > st; vector rank; LongestCommonPrefixArray() : sa(SuffixArray()) {} LongestCommonPrefixArray(const SuffixArray& sa) : sa(sa) { const string& s = sa.str; int n = s.size(); rank.resize(n + 1); for (int i = 0; i <= n; i++) rank[sa[i]] = i; lcp.resize(n + 1); lcp[0] = 0; for (int i = 0, h = 0; i < n; i++) { int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < n && i + h < n; h++) { if (s[j + h] != s[i + h]) break; } lcp[rank[i] - 1] = h; } st = SparseTable< RMQSL >(lcp); } int operator[](int idx) const { return lcp[idx]; } int getLCP(int i, int j) { i = rank[i], j = rank[j]; if (i > j) swap(i, j); return st.query(i, j); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; string all_s = ""; vector ids(n), len(n); for (int i = 0; i < n; i++) { string s; cin >> s; ids[i] = all_s.size(); len[i] = s.size(); all_s += s; } SuffixArray sa(all_s); LongestCommonPrefixArray lcp(sa); int m; ll x, d; cin >> m >> x >> d; ll ans = 0; for (int k = 1; k <= m; k++) { ll i = (x / (n - 1)) + 1; ll j = (x % (n - 1)) + 1; if (i > j) swap(i, j); else j++; int min_len = min(len[i - 1], len[j - 1]); i = ids[i - 1]; j = ids[j - 1]; ans += min(min_len, lcp.getLCP(i, j)); x = (x + d) % ((ll)n * (n - 1)); } cout << ans << "\n"; return 0; }