#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long #define uint unsigned int using namespace std; const int N=1e5+10,M=2075,SZ=1.1e6+50; const int LM=1510; const int B=45; int n,m,q; string t[M],s[N]; string str[SZ]; //int len[SZ];//,id[SZ]; //uint val[SZ]; //int last[SZ],X[SZ],Y[SZ]; vector<int> vec[SZ]; const int base=131,mod=1e9+9; struct Node{ int id,l,r; Node(){id=0,l=0,r=0;} Node(int _id,int _l,int _r){id=_id,l=_l,r=_r;} }; unordered_map<int,Node> To[2]; mt19937_64 rng(9517); int XOR=rng()%mod; struct ACAM{ int trie[M][26];uint cnt[M]; int fail[M],fa[M],id[M];int tot=0; //uint cnt2[M][M]; //uint len[M]; void insert(string s){ int now=0; for(auto ch:s){ int op=ch-'a'; if(!trie[now][op]) trie[now][op]=++tot,fa[tot]=now,id[tot]=op;//len[tot]=len[now]+1; now=trie[now][op]; }cnt[now]++; //for(int i=len[now];i<=LM;i++) cnt2[now][i]++; } void build(){ queue<int> q; for(int i=0;i<=25;i++) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()){ int p=q.front();q.pop(); for(int i=0;i<=25;i++){ if(trie[p][i]){ fail[trie[p][i]]=trie[fail[p]][i]; q.push(trie[p][i]); }else{ trie[p][i]=trie[fail[p]][i]; } } cnt[p]+=cnt[fail[p]]; //for(int i=0;i<=LM;i++) cnt2[p][i]+=cnt2[fail[p]][i]; } } }A[2]; int dt[N],LEN=0,MX=0; int cost=0; struct Tree{ int lg[M<<1],leaf[M],dep[M<<1],L[M<<1],R[M<<1]; short pre[15][M][M][2],suf[15][M][M][2]; int lca(int x,int y){ return x>>lg[x^y]; } string str[2];int len; void build(int p,int l,int r){ dep[p]=dep[p/2]+1;L[p]=l,R[p]=r;cost++; //cout<<l<<' '<<r<<endl; if(l==r){ leaf[l]=p; }else{ build(p*2,l,(l+r)/2);build(p*2+1,(l+r)/2+1,r); }int d=dep[p]; for(int i=0;i<=LEN;i++){ for(int o=0;o<=1;o++) pre[d][l][i][o]=A[o].trie[i][str[o][l]-'a'];//cout<<"p: "<<l<<' '<<r<<' '<<pre[d][l][i][o]<<endl; } //cout<<l<<' '<<r<<endl; for(int pos=l+1;pos<=r;pos++){ for(int i=0;i<=LEN;i++){ for(int o=0;o<=1;o++) pre[d][pos][i][o]=A[o].trie[pre[d][pos-1][i][o]][str[o][pos]-'a']; } } for(int i=0;i<=LEN;i++){ for(int o=0;o<=1;o++) suf[d][r][i][o]=A[o].trie[i][str[o][r]-'a']; } for(int pos=r-1;pos>=l;pos--){ for(int i=0;i<=LEN;i++){ for(int o=0;o<=1;o++) suf[d][pos][i][o]=suf[d][pos+1][A[o].trie[i][str[o][pos]-'a']][o]; } } //if(l==r){ // cout<<l<<' '<<pre[d][l][1][0]<<endl; //} } void init(){ int x=1;while(x<str[0].length()) x<<=1; while(str[0].length()<x) str[0]+='a'; while(str[0].length()<x) str[1]+='a';len=x; for(int i=1;i<=(x<<1);i++) lg[i]=lg[i/2]+1; memset(pre,0,sizeof(pre));memset(suf,0,sizeof(suf)); str[0]=' '+str[0];str[1]=' '+str[1];build(1,1,len); } int query(int l,int r,int x,int op){ if(l==r){ return pre[dep[leaf[l]]][l][x][op]; }else{ int p=lca(leaf[l],leaf[r]); //cout<<l<<' '<<r<<' '<<x<<' '<<op<<' '<<leaf[l]<<' '<<leaf[r]<<endl; return pre[dep[p*2+1]][r][suf[dep[p*2]][l][x][op]][op]; } } }T; int id[SZ][2],hsh[SZ][2],len[SZ]; uint v[M][M],val[SZ]; int pb[M]; void slv(){ cin>>n>>m>>q; for(int i=1;i<=n;i++) cin>>t[i]; for(int i=1;i<=m;i++) cin>>s[i]; for(int i=1;i<=n;i++){ dt[i]=LEN;LEN+=t[i].length(); string rev=t[i];reverse(rev.begin(),rev.end()); A[0].insert(t[i]);A[1].insert(rev); T.str[0]+=t[i],T.str[1]+=rev; int h1=0,h2=0; for(int j=0;j<t[i].length();j++){ h1=0,h2=0; for(int k=j;k<t[i].length();k++){ h1=(1ll*h1*base+t[i][k])%mod; h2=(1ll*h2*base+rev[k])%mod; To[0][h1^XOR]=(Node){i,j+1,k+1}; To[1][h2^XOR]=(Node){i,j+1,k+1}; } } }MX=LEN+10; A[0].build();A[1].build();T.init(); cerr<<cost<<endl; //for(int i=1;i<=6;i++) cout<<A[0].cnt[i]<<' ';cout<<endl; for(int i=1;i<=A[1].tot;i++){ for(int j=0;j<=A[0].tot;j++){ int op=A[1].id[i]; int now=A[0].trie[j][op]; v[j][i]=v[now][A[1].fa[i]]+A[0].cnt[now]; if(j!=0) v[j][i]-=v[0][i]; //cout<<j<<' '<<i<<' '<<v[j][i]<<' '<<now<<' '<<A[0].cnt[now]<<endl; }v[0][i]=0; } for(int i=1;i<=m;i++){ int now1=0,now2=0; int h1=0,h2=0;len[i]=s[i].length(); string rev=s[i];reverse(rev.begin(),rev.end()); for(int j=0;j<s[i].length();j++){ now1=A[0].trie[now1][s[i][j]-'a']; now2=A[1].trie[now2][rev[j]-'a']; h1=(1ll*h1*base+s[i][j])%mod; h2=(1ll*h2*base+rev[j])%mod; val[i]+=A[0].cnt[now1]; }id[i][0]=now1,id[i][1]=now2; hsh[i][0]=h1,hsh[i][1]=h2; cout<<val[i]<<'\n';//cout<<"id:"<<id[i][0]<<endl; //str[i]=s[i]; } pb[0]=1;for(int i=1;i<=MX;i++) pb[i]=1ll*pb[i-1]*base%mod; for(int i=m+1;i<=m+q;i++){ int x,y;cin>>x>>y;//str[i]=str[x]+str[y]; len[i]=min(len[x]+len[y],MX); hsh[i][0]=(1ll*hsh[x][0]*pb[len[y]]+hsh[y][0])%mod; hsh[i][1]=(1ll*hsh[y][0]*pb[len[x]]+hsh[x][0])%mod; val[i]=val[x]+val[y]+v[id[x][0]][id[y][1]]; //cout<<id[x][0]<<' '<<id[y][1]<<' '<<x<<' '<<y<<endl; Node dx=To[1][hsh[x][1]^XOR],dy=To[0][hsh[y][0]^XOR]; if(!dy.id||len[y]==MX){ id[i][0]=id[y][0]; }else{ //cout<<dt[dy.id]+dy.l<<' '<<dt[dy.id]+dy.r<<endl; id[i][0]=T.query(dt[dy.id]+dy.l,dt[dy.id]+dy.r,id[x][0],0); } if(!dx.id||len[x]==MX){ id[i][1]=id[x][1]; }else{ //cout<<dt[dx.id]+dx.l<<' '<<dt[dx.id]+dx.r<<endl; id[i][1]=T.query(dt[dx.id]+dx.l,dt[dx.id]+dx.r,id[y][1],1); }cout<<val[i]<<'\n';//cout<<"id:"<<id[i][0]<<endl; //cout<<i<<' '<<str[i]<<' '<<id[i][0]<<' '<<id[i][1]<<endl; } } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1;//cin>>t; while(t--) slv();cout.flush(); return 0; }