#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; } typedef int TABLE_TYPE; const int SMALL = 5; namespace TABLE{ /* s=2^SMALL l=MAX_SIZE/SMALL */ const int SIZE = 1<<21; const int LARGE = SIZE>>SMALL; TABLE_TYPE L[2][SIZE]; TABLE_TYPE S[2][SIZE*(SMALL+1)]; const int B=1<=-1) rl[k+i]=min(rl[k-l_sz+i],rl[k-l_sz+i-b]); } for(int k = sz,b=1,r=0 ;b*2<=sz&&b<(1<=-1) rs[k+i]=min(rs[k-sz+i],rs[k-sz+i-b]); DEBUG if(i==7) printf("ls[%d][%d]=%d\n",i,k-sz,ls[k+i-sz]); } } T get(int l,int r){ DEBUG printf("mst::get(l=%d,r=%d)\n",l,r); if(l>r)swap(l,r); int k=min(SMALL,31-__builtin_clz(r-l+1))*sz; T res=min(ls[k+l],rs[k+r]); DEBUG printf("mst::small_query(l=%d,r=%d,k=%d)=%d\n",l,r,k,res); l=l/B+1; r=r/B-1; if(r &v) :ll(TABLE::L[0]), rl(TABLE::L[1]), ls(TABLE::S[0]), rs(TABLE::S[1]){ sz=v.size(); B=TABLE::B; ls[0]=rs[0]=0; REP(i,sz){ ls[i+1]=rs[i+1]=ls[i]+v[i]; if(i%B==0)ll[i/B]=rl[i/B]=ls[i]; else ll[i/B]=rl[i/B]=min(ll[i/B],ls[i]); } ll[sz/B]=rl[sz/B]=ls[sz]; l_sz=sz/B+1; sz++; build(); } }; char s[812345]; typedef vector V; V input(int 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++)='\0';len++; } id.back()=len; *(ss++)='\0'; return id; } struct node{ int nxt[26]; int pos; }; namespace trie{ const int SZ = 812345; node tree[SZ]; int sz=0; int add_node(){ REP(j,26)tree[sz].nxt[j]=-1; return sz++; } void init(){ add_node(); } int insert(char* p){ int now=0; while(*p!='\0'){ int &nxt=tree[now].nxt[(*p)-'a']; if(nxt==-1)nxt=add_node(); now=nxt; p++; } return now; } void dfs(int v,V &seq){ tree[v].pos=seq.size(); REP(i,26)if(tree[v].nxt[i]!=-1){ seq.pb(+1); dfs(tree[v].nxt[i],seq); seq.pb(-1); } } V get_seq(){ V seq; seq.reserve(2*sz+10); dfs(0,seq); return seq; } } int main(){ int N; scanf("%d",&N); auto id = input(N); string str=s; trie::init(); if(N==100000)return 0; REP(i,N)id[i]=trie::insert(s+id[i]); LL x,d,M; scanf("%lld %lld %lld",&M,&x,&d); auto seq=trie::get_seq(); min_sparse_table rmq(seq); 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--; i=trie::tree[id[i]].pos; j=trie::tree[id[j]].pos; int k = rmq.get(i,j); DEBUG cout<