#include using namespace std; typedef long long LL; #define fin "\n" #define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define DEBUG if(0) #define REC(ret, ...) std::function template inline bool chmin(T &l,T r) {bool a=l>r;if(a)l=r;return a;} template inline bool chmax(T &l,T r) {bool a=l istream& operator>>(istream &is,vector &v){ for(auto &it:v)is>>it; return is; } /* sa[0]=n //空文字列 lcp[i]:=suffix[sa[i]]とsuffix[sa[i+1]]の共通高さ */ namespace latte{ void create_begin_bucket(vector&v,vector&bucket){ fill(bucket.begin(),bucket.end(),0); for(int i=0;i&v,vector&bucket){ fill(bucket.begin(),bucket.end(),0); for(int i=0;i&v,vector&sa,int mv,vector&bucket,vector&is_l){ create_begin_bucket(v,bucket); for(int i=0;i0&&is_l[sa[i]-1])sa[bucket[v[sa[i]-1]]++]=sa[i]-1; } void invert_induced_sort(vector&v,vector&sa,int mv,vector&bucket,vector&is_l){ create_end_bucket(v,bucket); for(int i=v.size()-1;i>=0;i--)if(sa[i]>0&&!is_l[sa[i]-1])sa[--bucket[v[sa[i]-1]]]=sa[i]-1; } vectorsa_is(vectorv,int mv){ if(v.size()==1)return vector(1,0); vectoris_l(v.size()); vectorbucket(mv+1); vectorsa(v.size(),-1); auto is_lms=[&](int x)->bool{return x>0&&is_l[x-1]&&!is_l[x];}; is_l[v.size()-1]=0; for(int i=v.size()-2;i>=0;i--)is_l[i]=v[i]>v[i+1]||(v[i]==v[i+1]&&is_l[i+1]); create_end_bucket(v,bucket); for(int i=0;iorder(v.size()); for(int i=0;inext_v(cur); cur=-1; int prev=-1; for(int i=0;i0&&is_lms(sa[i]+d))break; } if(diff){cur++;prev=sa[i];} next_v[order[sa[i]]]=cur; } vectorre_order(next_v.size()); for(int i=0;inext_sa=sa_is(next_v,cur); create_end_bucket(v,bucket); for(int i=0;i=0;i--)sa[--bucket[v[re_order[next_sa[i]]]]]=re_order[next_sa[i]]; induced_sort(v,sa,mv,bucket,is_l); invert_induced_sort(v,sa,mv,bucket,is_l); return sa; } vector sa_is(string &s){ vectorv(s.size()+1); for(int i=0;i construct_sa(string& S) { return latte::sa_is(S); n = S.size(); vector sa(n + 1); for (int i = 0; i <= n; i++) { sa[i] = i; R[i] = i < n ? S[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa.begin(), sa.end(), compare_sa); T[sa[0]] = 0; for (int i = 1; i <= n; i++) T[sa[i]] = T[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); for (int i = 0; i <= n; i++) R[i] = T[i]; } return sa; } vector construct_lcp(string& S, vector &sa) { n = S.size(); for (int i = 0; i <= n; i++)R[sa[i]] = i; int h = 0; vector lcp(n + 1, 0); for (int i = 0; i < n; i++) { int j = sa[R[i] - 1]; if (h > 0)h--; for (; j + h < n&&i + h < n; h++) { if (S[j + h] != S[i + h])break; } lcp[R[i] - 1] = h; } return lcp; } } namespace TABLE{ #define SIZE 8000000 int mem[2][SIZE]; //#defube CNT 100 //int cnt=0; //int mems[CNT][SIZE]; }; template class min_sparse_table{ private: T *L,*R;int _size; void build(){ for(int k = _size,b=1 ;b*2<=_size; k+=_size,b<<=1) for(int i = 0; i < _size; i++){ if(i+b*2<=_size) L[k+i]=min(L[k-_size+i],L[k-_size+i+b]); if(i-b*2>=-1) R[k+i]=min(R[k-_size+i],R[k-_size+i-b]); } } public:/*methods*/ int size(){return _size;} T get(int l,int r){ int k=(31-__builtin_clz(r-l+1))*_size; return min(L[k+l],R[k+r]); } min_sparse_table(std::vector &v) :L(TABLE::mem[0]),R(TABLE::mem[1]){ _size=v.size(); for(int i = 0; i < _size; i++)L[i]=R[i]=v[i]; build(); } min_sparse_table(T* v,int n) :L(TABLE::mem[0]),R(TABLE::mem[1]){ _size=n; for(int i = 0; i < _size; i++)L[i]=R[i]=v[i]; build(); } }; char s[912345]; int main(){ int N; scanf("%d",&N); char *ss=s; vector id(N+1); int len=0; REP(i,N){ scanf("%s",ss); id[i]=len; while(*ss !='\0'){ ss++;len++; } *(ss++)='$';len++; } id.back()=len; *(ss++)='\0'; string str=s; LL x,d,M; scanf("%lld %lld %lld",&M,&x,&d); auto sa = SA::construct_sa(str); auto cww=sa; REP(i,sa.size()){ cww[sa[i]]=i; } auto lcp = SA::construct_lcp(str,sa); min_sparse_table rmq(lcp); //return 0; LL res=0; REP(q,M){ LL i = x/(N-1)+1; LL j = x%(N-1)+1; if(i>j)swap(i,j); else j++; i--,j--; int ij=min(id[i+1]-id[i],id[j+1]-id[j])-1; i=cww[id[i]]; j=cww[id[j]]; if(i>j)swap(i,j); if(i==j){ res+=id[i+1]-id[i]-1; //cout<<"a"<