#include using namespace std; using ll = long long; struct SuffixArray { string str; vector sa; vector rank; // saの逆関数に相当 SuffixArray() {} // O(N log N) SuffixArray(const string& s) : str(s) { if (str.empty()) return; int n = str.size(); sa.resize(n, 0); rank.resize(n, 0); if (n == 1) return; // 長さ1のソート constexpr int CHAR_NUM = 256; vector cnt(max(n, CHAR_NUM), 0); for (int i = 0; i < n; i++) { cnt[str[i]]++; } for (int i = 1; i < CHAR_NUM; i++) { cnt[i] += cnt[i - 1]; } for (int i = 0; i < n; i++) { sa[--cnt[str[i]]] = i; } rank[sa[0]] = 0; int classes = 1; for (int i = 1; i < n; i++) { if (str[sa[i]] != str[sa[i - 1]]) classes++; rank[sa[i]] = classes - 1; } // 長さlen*2のソート int len; auto equal_class = [&](const int i, const int j) { if (rank[i] != rank[j]) return false; else { int ri = (i + len < n ? rank[i + len] : -1); int rj = (j + len < n ? rank[j + len] : -1); return ri == rj; } }; vector tmp_sa(n), tmp_rank(n); for (len = 1; len < n; len <<= 1) { fill(cnt.begin(), cnt.begin() + classes, 0); for (int i = 0; i < n; i++) { cnt[rank[sa[i]]]++; } for (int i = 1; i < classes; i++) { cnt[i] += cnt[i - 1]; } for (int i = n - 1; i >= 0; i--) { if (sa[i] + len >= n) tmp_sa[i] = sa[i]; if (sa[i] >= len) { int s1 = sa[i] - len; tmp_sa[--cnt[rank[s1]]] = s1; } } sa.swap(tmp_sa); tmp_rank[sa[0]] = 0; classes = 1; for (int i = 1; i < n; i++) { if (!equal_class(sa[i-1], sa[i])) classes++; tmp_rank[sa[i]] = classes - 1; } rank.swap(tmp_rank); } } int operator[](int idx) const { return sa[idx]; } // 文字列s以上となる最小の接尾辞について、SAのindexを返す(無いならsa.size()を返す) int lower_bound(const string& s) const { 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) const { 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) const { 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; LongestCommonPrefixArray() : sa(SuffixArray()) {} LongestCommonPrefixArray(const SuffixArray& sa) : sa(sa) { const string& s = sa.str; const vector& rank = sa.rank; int n = s.size(); lcp.resize(n - 1); for (int i = 0, h = 0; i < n; i++) { if (h > 0) h--; if (rank[i] == 0) continue; for (int j = sa[rank[i] - 1]; 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]; } // sa.str.substr(i) と sa.str.substr(j) のLCPを求める int getLCP(int i, int j) { i = sa.rank[i], j = sa.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; }