#include using namespace std; using ll = long long; // #undef DEBUG // #define DEBUG /// {{{ DEBUG --- /// #ifdef DEBUG template ostream &operator<<(ostream &o, const vector &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 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 ostream &operator<<(ostream &o, const vector &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 typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple const &){} template typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple const & t){ os << (n==0?"":", ") << get(t); _ot(os, t); } template ostream & operator<<(ostream &o, tuple const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; } template ostream & operator<<(ostream &o, pair const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; } /// }}}--- /// // Mamber & Mayers // SA // *1 : if you want original comparison rule, change here struct SA { const int n; const string &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(n) { iota(begin(sa), end(sa), 0); sort(begin(sa), end(sa), [&](int a, int b) { return s[a] < s[b]; }); // *1 for(int i = 0; i < n; i++) rnk[i] = s[i]; // *1 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; } } }; struct LCP { const int n; const string &s; vector< int > lcp; int operator[](int i) const { return lcp[i]; } LCP(const SA& sa) : n(sa.n), s(sa.s), lcp(n - 1) { int h = 0; for(int i = 0; i < n - 1; i++) { int j = sa[sa.rnk[i] - 1]; if(h) h--; 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 struct SparseTable { using T = typename SemiLattice::T; std::size_t n; std::vector log2; std::vector< std::vector > t; T identity; SparseTable():n(0) {} SparseTable(std::size_t n, T identity = T()): n(n), log2(n + 1), identity(identity) { for(std::size_t i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1; t.resize(log2[n] + 1, std::vector(n, identity)); } template::value_type> SparseTable(InputIter first, InputIter last, T identity = T()) : SparseTable(std::distance(first, last), identity) { std::copy(first, last, std::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(std::size_t j = 0; j < log2[n]; j++) { std::size_t w = 1 << j; for(std::size_t i = 0; i + (w << 1) <= n; i++) { t[j + 1][i] = SemiLattice::op(t[j][i], t[j][i + w]); } } } T query(std::size_t l, std::size_t r) { if(r - l < 1) return identity; std::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 idx(n); vector len(n); for(int i = 0; i < n; i++) { string t; cin >> t; idx[i] = s.size(); len[i] = t.size(); s += t + "-"; } SA sa(s); LCP lcp(sa); SparseTable 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]); i = idx[i]; j = idx[j]; i = sa.rnk[i]; j = sa.rnk[j]; a = min(a, (int) ecas.query(min(i,j), max(i,j))); ans += a; } cout << ans << endl; return 0; }