#include "bits/stdc++.h" // #pragma GCC optimize("Ofast,unroll-loops") // #pragma GCC target("avx2,tune=native") using namespace std; #define int long long #define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i) #define FORD(i, a, b) for (int i = (a), _##i = (b); i >= _##i; --i) #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) #define DEBUG(X) { auto _X = (X); cerr << "L" << __LINE__ << ": " << #X << " = " << (_X) << endl; } #define PR(A, n) { cerr << "L" << __LINE__ << ": " << #A << " = "; FOR(_, 1, n) cerr << A[_] << ' '; cerr << endl; } #define PR0(A, n) { cerr << "L" << __LINE__ << ": " << #A << " = "; REP(_, n) cerr << A[_] << ' '; cerr << endl; } #define __builtin_popcount __builtin_popcountll #define SZ(x) ((int)(x).size()) #define ALL(a) (a).begin(), (a).end() #define TWO(x) (1LL<<(x)) inline int gcd(int a, int b) {int r; while (b) {r = a % b; a = b; b = r;} return a;} // For printing pair, container, etc. // Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html template ostream& operator << (ostream& out, const pair& p) { return out << '(' << p.first << ", " << p.second << ')'; } template()))> typename enable_if::value, ostream&>::type operator << (ostream& out, const Con& con) { out << '{'; for (auto beg = con.begin(), it = beg; it != con.end(); it++) { out << (it == beg ? "" : ", ") << *it; } return out << '}'; } template ostream& print_tuple_utils(ostream& out, const T& tup) { if (i == tuple_size::value) return out << ")"; else return print_tuple_utils(out << (i ? ", " : "(") << get(tup), tup); } template ostream& operator << (ostream& out, const tuple& t) { return print_tuple_utils<0, tuple>(out, t); } // for 64-bit, use mt19937_64 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int get_rand(int r) { return uniform_int_distribution (0, r-1)(rng); } // use shuffle instead of random_shuffle #define random_shuffle askcjaljc inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) { unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m; #ifdef __GNUC__ asm( "divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (y) ); #else __asm { mov edx, dword ptr[xh]; mov eax, dword ptr[xl]; div dword ptr[y]; mov dword ptr[d], eax; mov dword ptr[m], edx; }; #endif out_d = d; out_m = m; } template struct ModInt { unsigned x; constexpr ModInt() : x(0) { } constexpr ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } #define COMPAREOP(OP) bool constexpr operator OP(ModInt b) const { return x OP b.x; } COMPAREOP(==) COMPAREOP(!=) COMPAREOP(<) COMPAREOP(>) COMPAREOP(<=) COMPAREOP(>=) #undef COMPAREOP ModInt operator-() const { return ModInt(x ? MOD - x : 0); } ModInt constexpr& operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt constexpr& operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { unsigned dummy; fasterLLDivMod((unsigned long long)x * that.x, MOD, dummy, x); return *this; } ModInt operator*(ModInt that) const { ModInt res; unsigned dummy; fasterLLDivMod((unsigned long long)x * that.x, MOD, dummy, res.x); return res; } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } // Below: copied from user202729_, not tested. ModInt inv() const { int a = x, b = MOD, ax = 1, bx = 0; while (b) { int q = a/b, t = a%b; a = b; b = t; t = ax - bx*q; ax = bx; bx = t; } assert(a == 1); if (ax < 0) ax += MOD; return ax; } ModInt& operator /= (ModInt m) { return (*this) *= m.inv(); } ModInt operator / (ModInt that) const { return ModInt(*this) /= that; } }; template ModInt power(ModInt n, long long k) { if (k == 0) return ModInt (1); ModInt res(1); while (k > 0) { if (k & 1) res = res * n; n = n * n; k >>= 1; } return res; } const int MOD = 1e9 + 7; using modular = ModInt; std::ostream& operator << (std::ostream& cout, const modular& m) { cout << m.x; return cout; } std::istream& operator >> (std::istream& cin, modular& m) { cin >> m.x; return cin; } struct Hash { long long x; modular y; Hash operator + (const Hash& a) const { return Hash{x + a.x, y + a.y}; } Hash operator - (const Hash& a) const { return Hash{x - a.x, y - a.y}; } Hash operator * (const Hash& a) const { return Hash{x * a.x, y * a.y}; } Hash operator * (int k) const { return Hash{x*k, y*k}; } }; bool operator == (const Hash& a, const Hash& b) { return a.x == b.x && a.y == b.y; } struct HashGenerator { HashGenerator(int maxLen, int base = 311) { p.resize(maxLen + 1); p[0] = {1, 1}; for (int i = 1; i <= maxLen; i++) { p[i] = p[i-1] * base; } } std::vector hash(const std::string& s) { std::vector res(s.size()); for (size_t i = 0; i < s.size(); i++) { res[i] = p[i] * (int) s[i]; } std::partial_sum(res.begin(), res.end(), res.begin()); return res; } // compare [l1, r1] vs [l2, r2] bool equals( const std::vector& h1, int l1, int r1, const std::vector& h2, int l2, int r2) { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); return __getHash(h1, l1, r1) * p[l2] == __getHash(h2, l2, r2) * p[l1]; } // Returns length of max common prefix of h1[l1, r1] and h2[l2, r2] // length = 0 -> first character of 2 substrings are different. int maxCommonPrefix( const std::vector& h1, int l1, int r1, const std::vector& h2, int l2, int r2) { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); int len1 = r1 - l1 + 1; int len2 = r2 - l2 + 1; auto r = std::views::iota(0, std::min(len1, len2)); auto res = std::ranges::partition_point( r, [&] (int mid) { return equals(h1, l1, l1+mid, h2, l2, l2+mid); }); return *res; } // compare s1[l1, r1] and s2[l2, r2] int cmp( const std::string& s1, const std::vector& h1, int l1, int r1, const std::string& s2, const std::vector& h2, int l2, int r2) { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); int commonPrefixLen = maxCommonPrefix(h1, l1, r1, h2, l2, r2); char c1 = (l1 + commonPrefixLen <= r1) ? s1[l1 + commonPrefixLen] : 0; char c2 = (l2 + commonPrefixLen <= r2) ? s2[l2 + commonPrefixLen] : 0; return (c1 == c2) ? 0 : ((c1 < c2) ? -1 : 1); } private: std::vector p; // DO NOT USE, this doesn't divide by p[l] Hash __getHash(const std::vector& h, int l, int r) { assert(0 <= l && l <= r && r < (int) h.size()); return h[r] - (l == 0 ? Hash{0, 0} : h[l-1]); } }; HashGenerator g(1000111); int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; std::cin >> n; std::vector> hs; for (int i = 0; i < n; i++) { std::string s; std::cin >> s; hs.push_back(g.hash(s)); } int m; long long x, d, res = 0; std::cin >> m >> x >> d; while (m--) { int i = x / (n - 1); int j = x % (n - 1); if (i <= j) ++j; x = (x + d) % (n * (n-1LL)); res += g.maxCommonPrefix( hs[i], 0, SZ(hs[i]) - 1, hs[j], 0, SZ(hs[j]) - 1); } std::cout << res << '\n'; return 0; }