#include #include #include #include #include using namespace std; #define REP(i,x) for(int i = 0; i < (int)(x); i++) // LCPを計算する O(N) vector build_lcp(const string &s, vector sa){ int n = s.size(), h = 0; vector rank(n + 1), lcp(n + 1); REP(i, n + 1) rank[sa[i]] = i; REP(i, n){ int j = sa[rank[i] - 1]; if(h > 0) h--; for(; j + h < n && i + h < n; h++){ if(s[j + h] != s[i + h])break; } lcp[rank[i] -1] = h; } return lcp; } class RMQ{ private: vector val; int n; public: RMQ(int size){ n=1; while(n(2*n,INT_MAX); } //x番目の要素をaに更新する void update(int x,int a){ x+=n-1; val[x]=a; while(x>0){ x=(x-1)/2; val[x]=min(val[x*2+1],val[x*2+2]); } } //a<=x> N; vector inv(N); vector > s(N); for(int i = 0; i < N; i++) { cin >> s[i].first; s[i].second = i; } sort(s.begin(), s.end()); for(int i = 0; i < N; i++) { inv[s[i].second] = i; } vector lcp(N - 1); for(int i = 0; i < N - 1; i++) { for(int j = 0; j < min(s[i].first.size(), s[i + 1].first.size()); j++) { if(s[i].first[j] == s[i + 1].first[j]) lcp[i] = j + 1; else break; } } RMQ rmq(N - 1); for(int i = 0; i < N - 1; i++) { rmq.update(i, lcp[i]); } int M; cin >> M; int64_t x, d; cin >> x >> d; int64_t answer = 0; for(int i = 0; i < M; i++) { int64_t ii = x / (N - 1); int64_t jj = x % (N - 1); if(ii > jj) { swap(ii, jj); } else { jj++; } int ipos = inv[ii]; int jpos = inv[jj]; if(ipos > jpos) swap(ipos, jpos); answer += rmq.minimum(ipos, jpos); x = (x + d) % (N * (N - 1)); } cout << answer << endl; }