#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 sasa{ bool is_lms(int index, const std::vector &sl_seq){ if(index+1 == (int)sl_seq.size())return true; if(0 < index && index < (int)sl_seq.size()){ return sl_seq[index] && !sl_seq[index-1]; } return false; } std::vector get_bucket(int* seq, const int n, const int alphabet_size){ std::vector bucket(alphabet_size); for(int i=0 ; i &is_type_s, int* arr, const int alphabet_size){ std::vector bucket = get_bucket(seq, n, alphabet_size); for(int i=0 ; i0 && !is_type_s[arr[i]-1]){ arr[bucket[seq[arr[i]-1]-1]++] = arr[i]-1; } } } void sort_type_s(int* seq, const int n, const std::vector &is_type_s, int* arr, const int alphabet_size){ std::vector bucket = get_bucket(seq, n, alphabet_size); for(int i=n-1 ; i>=0 ; i--){ if(arr[i] != -1 && arr[i]>0 && is_type_s[arr[i]-1]){ arr[--bucket[seq[arr[i]-1]]] = arr[i]-1; } } } void create_suffix_array(int* arr, int* seq, const int n, const int alphabet_size){ for(int i=0 ; i is_type_s(n); is_type_s[n-1] = true; for(int i=n-2 ; i>=0 ; i--){ if(seq[i] == seq[i+1])is_type_s[i] = is_type_s[i+1]; else is_type_s[i] = seq[i] < seq[i+1]; } std::vector bucket = get_bucket(seq, n, alphabet_size); for(int i=0 ; i < n ; i++){ if(is_lms(i, is_type_s))arr[--bucket[seq[i]]] = i; } sort_type_l(seq, n, is_type_s, arr, alphabet_size); sort_type_s(seq, n, is_type_s, arr, alphabet_size); // LMS-substringの元の数値列における位置を辞書順に左詰めで格納する int num_lms = 0; for(int i=0 ; i= num_lms ; i--){ if(arr[i] != -1)arr[p--] = arr[i]; } // 同じLMS-substringがある場合は再帰的に順序を求めるa if(next_alphabet_size != num_lms){ create_suffix_array(arr, arr+n-num_lms, num_lms, next_alphabet_size); for(int i=0 ; i < num_lms ; i++)arr[n-num_lms+arr[i]] = i; for(int i=0, p=0 ; i < n ; i++){ if(is_lms(i, is_type_s)){ arr[arr[n-num_lms+p]] = i; p++; } } } // 辞書順以外を一旦クリア for(int i=num_lms ; i= 0 ; i--){ bucket[seq[arr[i]]]--; std::swap(arr[bucket[seq[arr[i]]]], arr[i]); } sort_type_l(seq, n, is_type_s, arr, alphabet_size); sort_type_s(seq, n, is_type_s, arr, alphabet_size); } int latte[912345]; int malta[912345]; std::vector create_suffix_array_from_string(const std::string &str){ std::set _alphabet(str.begin(), str.end()); std::vector alphabet(_alphabet.begin(), _alphabet.end()); int n = str.size()+1; int* seq = latte; int* arr = malta; for(int i=0 ; i < n-1 ; i++)seq[i] = lower_bound(alphabet.begin(), alphabet.end(), str[i]) - alphabet.begin() + 1; create_suffix_array(arr, seq, n, alphabet.size()); return std::vector(arr, arr+n); } }; namespace SA { int n, k; int R[912345]; int T[912345]; bool compare_sa(int i, int j) { if (R[i] != R[j])return R[i] < R[j]; else { int ri = i + k <= n ? R[i + k] : -1; int rj = j + k <= n ? R[j + k] : -1; return ri < rj; } } vector construct_sa(string& S) { return sasa::create_suffix_array_from_string(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 3000000 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()){ //cout< rmq(lcp); 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"<