#line 1 "main.cpp" #include #include #include #include #include #include #line 3 "/home/kokoro601/compro_library/DataStructure/SparseTable.hpp" template class SparseTable { public: std::vector > tab; std::vector lookup; void build(const std::vector &v) { int b = 0; int n = v.size(); while (1 << b <= n) b++; tab.assign(b, std::vector(1 << b)); for (int i = 0; i < n; i++) tab[0][i] = v[i]; for (int i = 1; i < b; i++) { int pre_len = 1 << (i - 1); int ub = n - (1 << i); for (int j = 0; j <= ub; j++) { tab[i][j] = std::min(tab[i - 1][j], tab[i - 1][j + pre_len]); } } lookup.resize(v.size() + 1); for (int i = 2; i < lookup.size(); i++) lookup[i] = lookup[i >> 1] + 1; } // [l, r) inline T rmq(int l, int r) { // assert(l < r); int b = lookup[r - l]; return std::min(tab[b][l], tab[b][r - (1 << b)]); } }; #line 8 "main.cpp" using namespace std; using ll = long long; using Graph = vector >; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector s(n); vector lcp(n), rank(n), rank_rev(n); for (int i = 0; i < n; i++) cin >> s[i]; iota(rank_rev.begin(), rank_rev.end(), 0); sort(rank_rev.begin(), rank_rev.end(), [&](int a, int b) { return s[a] < s[b]; }); for (int i = 0; i < n; i++) rank[rank_rev[i]] = i; for (int i = 0; i < n; i++) { int j = 0; if (rank[i] + 1 == n) continue; int nxt_idx = rank_rev[rank[i] + 1]; for (; j < min(s[i].size(), s[nxt_idx].size()); j++) if (s[i][j] != s[nxt_idx][j]) break; lcp[rank[i]] = j; } SparseTable st; st.build(lcp); int m; ll x, d; cin >> m >> x >> d; ll ans = 0; for (int k = 0; k < m; k++) { ll i = (x / (n - 1)) + 1; ll j = (x % (n - 1)) + 1; if (i > j) swap(i, j); else j = j + 1; int rank1 = rank[i - 1]; int rank2 = rank[j - 1]; if (rank1 > rank2) swap(rank1, rank2); ans += st.rmq(rank1, rank2); x = (x + d) % (n * (n - 1)); } cout << ans << endl; return 0; }