#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; } /// }}}--- /// // 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; size_t n; vector log2; vector< vector > 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(n, identity)); t.resize(1); t.resize(1, vector()); } template::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; vector s(n); for(int i = 0; i < n; i++) cin >> s[i]; vector ord(n); iota(begin(ord), end(ord), 0); // O(NlogN + sum logN) ? sort(begin(ord), end(ord), [&](int a, int b){ return s[a] < s[b]; }); auto id = ord; for(int i = 0; i < n; i++) id[ord[i]] = i; vector lcp(n-1); for(int x = 0; x < n - 1; x++) { int i = ord[x]; int j = ord[x + 1]; while(lcp[x] < s[i].size() && lcp[x] < s[j].size() && s[i][lcp[x]] == s[j][lcp[x]]) lcp[x]++; } SparseTable ecas(begin(lcp), end(lcp), 1e9); int m; cin >> m >> x >> d; ll ans = 0; // while(m--) { // int i, j; // tie(i, j) = nx(); // i = id[i]; // j = id[j]; // if(i > j) swap(i, j); // ans += ecas.query(i, j); // } cout << ans << endl; return 0; }