#include using namespace std; class SuffixDataStructure { public: // a[i]>=0 SuffixDataStructure(const std::vector &a) : a(a) { sa = suffix_array(a); sa.insert(sa.begin(), a.size()); build_lcp(); build_rmq(); } int get_lcp(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); // 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; vector suffix_array(vector a) { const int n = a.size(); if (n == 0) return {}; constexpr int TYPE_L = 0, TYPE_S = 1; const auto mp = [](vector f, vector a) { for (int &x : a) x = f[x]; return a; }; const auto filter = [](auto f, vector a) { vector y; for (int &x : a) if (f(x)) y.push_back(x); return y; }; const auto seq = [](int n) { vector a(n); for (int i = 0; i < n; i++) a[i] = i; return a; }; const auto freq = [](vector a) { vector f(*max_element(a.begin(), a.end()) + 1); for (int x : a) f[x]++; return f; }; const auto tail = [](vector a) { a.erase(a.begin()); return a; }; const auto pairs = [](vector a) { vector> b; for (int i = 0; i + 1 < a.size(); i++) b.emplace_back(a[i], a[i + 1]); return b; }; const auto scanl = [](auto f, auto acc, auto a) { vector b(a.size() + 1); b.front() = acc; for (int i = 0; i < a.size(); i++) b[i + 1] = acc = f(acc, a[i]); return b; }; const auto scanr = [](auto f, auto acc, auto a) { vector b(a.size() + 1); b.back() = acc; for (int i = int(a.size()) - 1; i >= 0; i--) b[i] = acc = f(a[i], acc); return b; }; const auto runl = [](vector &a, auto pred, auto f) { for (int i = 0; i < a.size(); i++) if (pred(a[i])) f(a[i]); }; const auto runr = [](vector &a, auto pred, auto f) { for (int i = int(a.size()) - 1; i >= 0; i--) if (pred(a[i])) f(a[i]); }; const auto run_pairs = [](vector a, auto f) { for (int i = 0; i + 1 < a.size(); i++) f(a[i], a[i + 1]); }; const auto type = scanr([](pair a, int acc) { return a.first == a.second ? acc : a.first < a.second; }, TYPE_L, pairs(a)); const auto induced_sort = [&](vector lms) { vector sa(n, -1); auto L = scanl([](int a, int b) { return a + b; }, 0, freq(a)), S = tail(L), SS = S; sa[L[a.back()]++] = n - 1; auto is_type_l = [&](int k) { return k > 0 && type[k - 1] == TYPE_L; }; auto is_type_r = [&](int k) { return k > 0 && type[k - 1] == TYPE_S; }; runr(lms, [](int x) { return true; }, [&](int i) { sa[--SS[a[i]]] = i; }); runl(sa, is_type_l, [&](int i) { sa[L[a[i - 1]]++] = i - 1; }); runr(sa, is_type_r, [&](int i) { sa[--S[a[i - 1]]] = i - 1; }); return sa; }; const auto is_lms = [&](int k) { return k > 0 && type[k - 1] == TYPE_L && type[k] == TYPE_S; }; const auto lms = filter(is_lms, seq(n)); const auto next = scanr([is_lms](pair a, int acc) { return is_lms(a.second) ? a.second : acc; }, n, pairs(seq(n))); const auto cmp = [&a, &next](int i, int j) { return lexicographical_compare(a.begin() + i, a.begin() + next[i], a.begin() + j, a.begin() + next[j]); }; vector rank(n); run_pairs(filter(is_lms, induced_sort(lms)), [&](int i, int j) { rank[j] = rank[i] + cmp(i, j); }); return induced_sort(mp(lms, suffix_array(mp(rank, lms)))); } void build_lcp() { const int n = a.size(); 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 build_rmq() { 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; cin >> n; std::vector start(n); std::vector t; std::vector len(n); for (int i = 0; i < n; i++) { start[i] = t.size(); static char buf[800001]; scanf("%s", buf); int j; for (j = 0; buf[j] != 0; j++) { t.push_back(buf[j]); } len[i] = j; } SuffixDataStructure suf(t); int m; long long x, d; cin >> m >> x >> d; long long ans = 0; const long long N = 1LL * n * (n - 1); while (m--) { int i = x / (n - 1); int j = x % (n - 1); if (i > j) { std::swap(i, j); } else { j = j + 1; } x += d; if (x >= N) { x -= N; } ans += min(suf.get_lcp(start[i], start[j]), min(len[i], len[j])); } std::cout << ans << std::endl; }