#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! /// --- SegmentTree Library {{{ /// // struct Monoid { // using T = _underlying_set_; // static T op(const T& a, const T& b) { return _a_op_b_; } // static constexpr T identity() { return _identity_element_; } // }; template struct SegTree { private: using T = typename Monoid::T; int n; std::vector data; // call after touch data[i] void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); } public: SegTree(): n(0) {} SegTree(int n): n(n) { data.resize(n * 2, Monoid::identity()); } template::value_type> SegTree(InputIter first, InputIter last) : SegTree(std::distance(first, last)) { copy(first, last, std::begin(data) + n); // fill from deep for(int i = n - 1; i > 0; i--) prop(i); } void set(int i, const T& v) { data[i += n] = v; while(i >>= 1) prop(i); // propUp } T get(int i) { return data[i + n]; } T query(int l, int r) { T tmpL = Monoid::identity(), tmpR = Monoid::identity(); for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) tmpL = Monoid::op(tmpL, data[l++]); if(r & 1) tmpR = Monoid::op(data[--r], tmpR); } return Monoid::op(tmpL, tmpR); } inline void dum(int r = -1) { #ifdef DEBUG std::ostream & o = #ifdef USE_COUT std::cout #else std::cerr #endif ; if(r < 0) r = n; o << "{"; for(int i = 0; i < std::min(r, n); i++) o << (i ? ", " : "") << get(i); o << "}" << std::endl; #endif } }; /// }}}--- /// // Monoid examples {{{ constexpr long long inf = std::numeric_limits::max(); // using P = pair struct MonoidMin { using T = long long; static T op(const T& a, const T& b) { return std::min(a, b); } static constexpr T identity() { return inf; } }; struct MonoidSum { using T = long long; static T op(const T& a, const T& b) { return a + b; } static constexpr T identity() { return 0; } }; struct MonoidMax { using T = long long; static T op(const T& a, const T& b) { return std::max(a, b); } static constexpr T identity() { return -inf; } }; // }}} using RMQ = SegTree; 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); RMQ ecas(begin(lcp.lcp), end(lcp.lcp)); 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; }