#include #include template class sparce_table { private: std::vector log2; std::vector> range_min; public: sparce_table() {} template sparce_table(It l, It r) { int n = r - l; log2.resize(n + 1); log2[1] = 0; for (int i = 2; i <= n; ++i) log2[i] = log2[i / 2] + 1; range_min.emplace_back(l, r); for (int i = 1;; ++i) { int w = 1 << i; if (n + 1 < w) break; range_min.emplace_back(n + 1 - w); for (int l = 0; l < n + 1 - w; ++l) { range_min[i][l] = std::min(range_min[i - 1][l], range_min[i - 1][l + w / 2]); } } } T rmq(int l, int r) { int i = log2[r - l]; int rr = r - (1 << i); return std::min(range_min[i][l], range_min[i][rr]); } }; #include using namespace std; using ll = long long; #define FOR(i, a, b) for (int i = (a); i < int(b); ++i) #define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i) #define rep(i, n) FOR(i, 0, n) #define rep1(i, n) FOR(i, 1, int(n) + 1) #define rrep(i, n) RFOR(i, 0, n) #define rrep1(i, n) RFOR(i, 1, int(n) + 1) #define all(c) begin(c), end(c) const int MOD = 1000000007; template void __dump__(std::ostream &os, const T &first) { os << first; } template void __dump__(std::ostream &os, const First &first, const Rest &... rest) { os << first << ", "; __dump__(os, rest...); } #define dump(...) \ do { \ std::ostringstream os; \ os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \ __dump__(os, __VA_ARGS__); \ std::cerr << os.str() << std::endl; \ } while (0) int n; vector ss; int m, x, d; int lcp_len(const string &a, const string &b) { int i = 0; while (i < (int)a.size() && i < (int)b.size() && a[i] == b[i]) { ++i; } return i; } int main() { while (cin >> n) { ss.resize(n); rep(i, n) cin >> ss[i]; cin >> m >> x >> d; vector idx(n), ridx(n); iota(all(idx), 0); sort(all(idx), [&](int a, int b) { return ss[a] < ss[b]; }); rep(i, n) ridx[idx[i]] = i; vector i(m), j(m); rep(k, m) { i[k] = (x / (n - 1)) + 1; j[k] = (x % (n - 1)) + 1; if (i[k] > j[k]) swap(i[k], j[k]); else j[k] = j[k] + 1; x = (x + d) % (n * (n - 1)); } vector lcp(n - 1); rep(i, n - 1) lcp[i] = lcp_len(ss[idx[i]], ss[idx[i + 1]]); sparce_table st(all(lcp)); int res = 0; rep(k, m) { int a = ridx[i[k] - 1], b = ridx[j[k] - 1]; if (a > b) swap(a, b); res += st.rmq(a, b); } cout << res << endl; } }