#include using namespace std; using ll = long long; /// --- Ultra DEBUG {{{ /// #ifdef DEBUG template struct myvector: vector { T & operator[](int i) { struct CannotAccessNullPointer {} ex; if(i < 0 || (int) vector::size() <= i) { cerr << "accessed " << i << " but size is " << vector::size() << endl; throw ex; } return vector::operator[](i); } const T & operator[](int i) const { struct CannotAccessNullPointer {} ex; if(i < 0 || (int) vector::size() <= i) { cerr << "accessed " << i << " but size is " << vector::size() << endl; throw ex; } return vector::operator[](i); } myvector(size_t n = 0, T t = T()): vector(n, t) {} }; #define vector myvector #endif /// }}}--- /// // #undef DEBUG // #define DEBUG /// {{{ DEBUG --- /// #ifdef DEBUG template < typename T > ostream &operator<<(ostream &o, const vector< T > &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; } #ifdef USE_COUT #define dump(...) \ [&]() { \ auto __debug_tap = make_tuple(__VA_ARGS__); \ cout << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \ << "\n"; \ }() #else #define dump(...) \ [&]() { \ auto __debug_tap = make_tuple(__VA_ARGS__); \ cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \ << "\n"; \ }() #endif template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream &o = #ifdef USE_COUT cout; #else cerr; #endif for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; } } #else template < typename T > ostream &operator<<(ostream &o, const vector< T > &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; } #define dump(...) (42) #define dump2D(...) (42) #endif template < int n, class... T > typename enable_if< (n >= sizeof...(T)) >::type _ot(ostream &, tuple< T... > const &) {} template < int n, class... T > typename enable_if< (n < sizeof...(T)) >::type _ot(ostream &os, tuple< T... > const &t) { os << (n == 0 ? "" : ", ") << get< n >(t); _ot< n + 1 >(os, t); } template < class... T > ostream &operator<<(ostream &o, tuple< T... > const &t) { o << "("; _ot< 0 >(o, t); o << ")"; return o; } template < class T, class U > ostream &operator<<(ostream &o, pair< T, U > const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; } /// }}}--- /// /// --- SA with IS {{{ /// template < class _T = string, class U = char, int K = 256 > struct SA { using T = _T; const int n; const T & s; vector< int > rnk; vector< int > sa; int operator[](int i) const { return sa[i]; } SA(const string &s) : n(s.size()), s(s), rnk(n) { sa_is< T, U >(sa, s + U(0), K); // change if T != string sa.erase(begin(sa)); for(int i = 0; i < n; i++) rnk[sa[i]] = i; } template < class V = string, class W = char > void sa_is(vector< int > &sa, const V &s, int k) { int n = s.size(); vector< int > S(n); // or L // S.back() = 1; for(int i = n - 2; i >= 0; i--) { if(s[i] < s[i + 1]) S[i] = 1; else if(s[i] > s[i + 1]) S[i] = 0; else S[i] = S[i + 1]; } // vector< int > lms; for(int i = 0; i < n; i++) if(isLMS(S, i)) lms.emplace_back(i); auto seed = lms; vector< int > _sa; inducedSort(_sa, s, k, S, seed); sa.resize(0); for(auto el : _sa) if(isLMS(S, el)) sa.emplace_back(el); vector< int > nums(n, -1); int num = 0; nums[sa[0]] = 0; for(int x = 0; x < (int) sa.size() - 1; x++) { int i = sa[x], j = sa[x + 1]; int diff = 0; for(int d = 0; d < n; d++) { if(s[i + d] != s[j + d] || isLMS(S, i + d) != isLMS(S, j + d)) { diff = 1; break; } else if(d && (isLMS(S, i + d) || isLMS(S, j + d))) break; } if(diff) num++; nums[j] = num; } auto _nums = nums; nums.resize(0); for(int el : _nums) if(el != -1) nums.emplace_back(el); if(num + 1 < (int) nums.size()) { sa_is< vector< int >, int >(seed, nums, num + 1); } else { seed.resize(num + 1); for(int i = 0; i < num + 1; i++) seed[nums[i]] = i; } for(int &el : seed) el = lms[el]; inducedSort(sa, s, k, S, seed); } template < class V = string, class W = char > void inducedSort(vector< int > &sa, const V &s, int k, const vector< int > &S, const vector< int > &lms) { int n = s.size(); sa.resize(n), sa.assign(n, -1); vector< int > bin(k + 1, 0); for(W ch : s) bin[ch + 1]++; int sum = 0; for(int &el : bin) el = sum += el; // step 1 vector< int > count(k); for(auto it = rbegin(lms); it != rend(lms); ++it) { int i = *it; W ch = s[i]; sa[bin[ch + 1] - 1 - count[ch]] = i; count[ch]++; } // step 2 count.assign(k, 0); for(int i : sa) { if(i == -1 || i == 0) continue; if(S[i - 1]) continue; W ch = s[i - 1]; sa[bin[ch] + count[ch]] = i - 1; count[ch]++; } // step 3 count.assign(k, 0); for(auto it = rbegin(sa); it != rend(sa); ++it) { int i = *it; if(i == -1 || i == 0) continue; if(!S[i - 1]) continue; W ch = s[i - 1]; sa[bin[ch + 1] - 1 - count[ch]] = i - 1; count[ch]++; } } inline bool isLMS(const vector< int > &S, int i) { return i > 0 && !S[i - 1] && S[i]; } }; /// }}}--- /// #if 0 /// --- Suffix Array with Mamber & Mayers {{{ /// template struct SA { const int n; const T &s; vector< int > rnk; vector< int > sa; int operator[](int i) const { return sa[i]; } SA(const T &s) : n(s.size()), s(s), rnk(n), sa(n) { iota(begin(sa), end(sa), 0); sort(begin(sa), end(sa), [&](int a, int b) { return s[a] < s[b]; }); for(int i = 0; i < n; i++) rnk[i] = s[i]; for(int i = 1; i < n; i <<= 1) { auto comp = [&](int a, int b) { if(rnk[a] != rnk[b]) return rnk[a] < rnk[b]; a = a + i < n ? rnk[a + i] : -1; b = b + i < n ? rnk[b + i] : -1; return a < b; }; sort(begin(sa), end(sa), comp); auto tmp = rnk; tmp[sa[0]] = 0; for(int j = 1; j < n; j++) tmp[sa[j]] = tmp[sa[j - 1]] + comp(sa[j - 1], sa[j]); /// rnk = tmp; } } }; /// }}}--- /// #endif /// --- LCP Array Library {{{ /// template < class S = SA<> > struct LCP { using T = typename S::T; const int n; const T &s; vector< int > lcp; int operator[](int i) const { return lcp[i]; } LCP(const S &sa) : n(sa.n), s(sa.s), lcp(n - 1) { int h = 0; for(int i = 0; i < n; i++) { if(h) h--; if(sa.rnk[i] == 0) continue; int j = sa[sa.rnk[i] - 1]; while(i + h < n && j + h < n && s[i + h] == s[j + h]) h++; lcp[sa.rnk[i] - 1] = h; } } }; /// }}}--- /// // NOTE : query in range! /// --- Sparse Table Library {{{ /// // struct SemiLattice { // using T = _underlying_set_; // static T op(T const &a, T const &b) { return _a_op_b_; } // }; template < class SemiLattice > struct SparseTable { using T = typename SemiLattice::T; size_t n; vector< size_t > log2; vector< vector< T > > t; T identity; SparseTable() : n(0) {} SparseTable(size_t n, T identity = T()) : n(n), log2(n + 1), identity(identity) { for(size_t i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1; t.resize(log2[n] + 1, vector< T >(n, identity)); } template < class InputIter, class = typename iterator_traits< InputIter >::value_type > SparseTable(InputIter first, InputIter last, T identity = T()) : SparseTable(distance(first, last), identity) { copy(first, last, begin(t[0])); build(); } void set(size_t i, T val) { t[0][i] = val; } T get(size_t i) { return t[0][i]; } void build() { for(size_t j = 0; j < log2[n]; j++) { size_t w = 1 << j; for(size_t i = 0; i + (w << 1) <= n; i++) { t[j + 1][i] = SemiLattice::op(t[j][i], t[j][i + w]); } } } T query(size_t l, size_t r) { if(r - l < 1) return identity; size_t j = log2[r - l]; return SemiLattice::op(t[j][l], t[j][r - (1 << j)]); } }; /// }}}--- /// // sparse table expample {{{ struct RMQSL { using T = int; static T op(T const &a, T const &b) { return a < b ? a : b; } }; // }}} ll n; ll x, d; pair< int, int > nx() { int i = (x / (n - 1)), j = (x % (n - 1)); if(i > j) swap(i, j); else j++; x = (x + d) % (n * (n - 1)); return make_pair(i, j); } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n; string s; vector< int > idx(n); vector< int > len(n); for(int i = 0; i < n; i++) { string t; cin >> t; idx[i] = s.size(); len[i] = t.size(); s += t; } // dump(SA<>("abaab").rnk); // s += "-"; // sentinel SA<> sa(s); LCP<> lcp(sa); // dump(s); // dump(sa.rnk); // dump(lcp.lcp); SparseTable< RMQSL > ecas(begin(lcp.lcp), end(lcp.lcp), 1e9); int m; cin >> m >> x >> d; ll ans = 0; while(m--) { int i, j; tie(i, j) = nx(); int a = min(len[i], len[j]); // dump(i, j, n); i = idx[i]; j = idx[j]; i = sa.rnk[i]; j = sa.rnk[j]; // dump(i, j, s.size()); a = min(a, (int) ecas.query(min(i, j), max(i, j))); // dump(a); ans += a; } cout << ans << endl; return 0; }