#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef __int128 i128; typedef unsigned long long ull; typedef unsigned int uint; typedef long long ll; const ull base=131; const int maxn=2e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,q,tot,cnt; ull pw[maxn]; string s[1555]; int to[1555][50005]; int dt[1555][50005]; int X[maxn],Y[maxn]; map<int,map<int,int> >mpl[1555],mpr[1555]; struct{ int son[1555][26],fail[1555],cnt[1555],ct; void add(string s){ int u=0; for(char c:s){ if(!son[u][c-'a'])son[u][c-'a']=++ct; u=son[u][c-'a']; }cnt[u]++; } void bd(){ queue<int>q; up(i,0,25)if(son[0][i])q.push(son[0][i]); while(!q.empty()){ int u=q.front();q.pop(); cnt[u]+=cnt[fail[u]]; up(i,0,25) if(son[u][i])fail[son[u][i]]=son[fail[u]][i],q.push(son[u][i]); else son[u][i]=son[fail[u]][i]; } } }A; int p,c; map<int,int>nd[maxn]; void init(int l,int r,int P){ // if(p<=5)cout<<"init "<<p<<" "<<l<<" "<<r<<" "<<P<<endl; int mid=l+r>>1; if(l==r){ nd[p][l]=P; mpr[p][P][r]=++c; up(i,0,A.ct) to[i][c]=A.son[i][s[p][l]-'a'],dt[i][c]=A.cnt[to[i][c]]; return; } init(l,mid,P<<1),init(mid+1,r,P<<1|1); // cout<<"test "<<p<<" "<<P<<" "<<l<<" "<<mid<<" "<<r<<endl; mpl[p][P][mid]=++c; up(i,0,A.ct) to[i][c]=A.son[i][s[p][mid]-'a'],dt[i][c]=A.cnt[to[i][c]]; down(i,mid-1,l){ mpl[p][P][i]=++c; up(j,0,A.ct){ int o=A.son[j][s[p][i]-'a']; to[j][c]=to[o][c-1]; dt[j][c]=dt[o][c-1]+A.cnt[o]; } } mpr[p][P][mid+1]=++c; up(i,0,A.ct) to[i][c]=A.son[i][s[p][mid+1]-'a'],dt[i][c]=A.cnt[to[i][c]]; up(i,mid+2,r){ mpr[p][P][i]=++c; up(j,0,A.ct){ to[j][c]=A.son[to[j][c-1]][s[p][i]-'a']; dt[j][c]=dt[j][c-1]+A.cnt[to[j][c]]; } } } pi get(int p,int l,int r){ if(l==r)return m_p(mpr[p][nd[p][l]][l],0); int x=nd[p][l],y=nd[p][r]; // cout<<x<<" "<<y<<endl; int id=x>>__lg(x^y)+1; // cout<<"! "<<p<<" "<<id<<" "<<l<<" "<<r<<endl; // assert(mpl[p][id].count(l));assert(mpr[p][id].count(r)); return m_p(mpl[p][id][l],mpr[p][id][r]); } int qr(vector<int>a){ int u=0,res=0; for(int p:a)for(int q:{X[p],Y[p]})if(q)res+=dt[u][q],u=to[u][q]; return res; } struct Hash { ull sm;int len; }hs[maxn]; Hash operator+(Hash a,Hash b){ return (Hash){a.sm*pw[b.len]+b.sm,a.len+b.len}; } bool operator<(Hash a,Hash b){ if(a.sm!=b.sm)return a.sm<b.sm; return a.len<b.len; } Hash operator-(Hash a,Hash b){ return {a.sm-b.sm*pw[a.len-b.len],a.len-b.len}; } struct node { int A,B,C,D,sz; Hash ha,hb,hc,hd; uint res,len; }str[maxn]; map<Hash,pair<int,pi> >st; node operator+(node a,node b){ node c; c.res=a.res+b.res; c.len=a.len+b.len; vector<int>v1,v2; if(a.C)v1={a.C,a.D};else v1={a.D};c.res-=qr(v1); if(b.B)v2={b.A,b.B};else v2={b.A};c.res-=qr(v2); for(int p:v2)v1.p_b(p);c.res+=qr(v1); c.A=a.A,c.ha=a.ha,c.B=a.B,c.hb=a.hb; c.sz=a.sz+b.sz; auto mr=[&](Hash a,Hash b){ ++cnt; auto w=st[a+b]; auto it=get(w.p1,w.p2.p1,w.p2.p2); X[cnt]=it.p1,Y[cnt]=it.p2; }; if(a.sz==2&&st.count(a.hb+b.ha)){ mr(a.hb,b.ha); c.hb=a.hb+b.ha,c.B=cnt; } else if(a.sz==1){ if(st.count(a.ha+b.ha)){ mr(a.ha,b.ha); c.ha=a.ha+b.ha,c.A=cnt; c.hb=b.hb,c.B=b.B; } else c.hb=b.ha,c.B=b.A; } c.C=b.C,c.D=b.D,c.hc=b.hc,c.hd=b.hd; if(b.sz==2&&st.count(a.hd+b.ha)){ mr(a.hd,b.ha); c.hc=a.hd+b.ha,c.C=cnt; } else if(b.sz==1){ if(st.count(a.hd+b.ha)){ mr(a.hd,b.ha); c.hd=a.hd+b.ha,c.D=cnt; c.hc=a.hc,c.C=a.C; } else c.hc=a.hd,c.C=a.D; } c.sz-=st.count(a.hd+b.ha); c.sz=min(c.sz,3); return c; } void slv(){ n=read(),m=read(),q=read(); pw[0]=1;up(i,1,100000)pw[i]=pw[i-1]*base; up(i,1,n)cin>>s[i]; up(i,1,26)s[i+n].p_b(i+'a'-1); n+=26;up(i,1,n)A.add(s[i]);A.bd(); up(i,1,n) up(j,0,(int)s[i].size()-1){ Hash a={0,0}; up(k,j,(int)s[i].size()-1) a=a+(Hash){s[i][k],1},st[a]={i,{j,k}}; } for(p=1;p<=n;p++){ int x=s[p].size(); while(x&(x-1))x++,s[p].p_b('a'); init(0,x-1,1); } up(i,1,m){ string a;cin>>a; str[i].len=a.size(); hs[0]=(Hash){a[0],1};up(j,1,(int)a.size()-1)hs[j]=hs[j-1]+(Hash){a[j],1}; auto chk=[&](int l,int r){return st.count(l?hs[r]-hs[l-1]:hs[r]);}; int p=0; vector<int>vec; vector<Hash>H; auto ins=[&](int l,int r){H.p_b(l?hs[r]-hs[l-1]:hs[r]);auto w=st[l?hs[r]-hs[l-1]:hs[r]];auto w2=get(w.p1,w.p2.p1,w.p2.p2);++cnt;X[cnt]=w2.p1,Y[cnt]=w2.p2;vec.p_b(cnt);}; up(i,0,(int)a.size()-1)if(!chk(p,i))ins(p,i-1),p=i; ins(p,str[i].len-1); if(vec.size()==1) str[i].A=str[i].D=vec[0],str[i].B=str[i].C=0,str[i].ha=str[i].hd=H[0],str[i].sz=1; else str[i].A=vec[0],str[i].ha=H[0],str[i].B=vec[1],str[i].hb=H[1],str[i].C=vec[vec.size()-2],str[i].hc=H[H.size()-2],str[i].D=vec.back(),str[i].hd=H.back();str[i].sz=min((int)vec.size(),3); str[i].res=qr(vec); // cout<<"-----------------------------"<<endl; // cout<<str[i].res<<" "<<str[i].len<<endl; // cout<<str[i].A<<" "<<str[i].B<<" "<<str[i].C<<" "<<str[i].D<<endl; } up(i,m+1,m+q){ int x=read(),y=read(); str[i]=str[x]+str[y]; // cout<<str[i].res<<" "<<str[i].len<<" "<<str[i].A<<" "<<str[i].B<<" "<<str[i].C<<" "<<str[i].D<<endl; } up(i,1,m+q)printf("%u\n",str[i].res-str[i].len); } int main(){ // freopen("1.in","r",stdin),freopen("1.out","w",stdout); // int t=read();while(t--)slv(); slv(); return 0; }