#include<bits/stdc++.h> using namespace std; #define ll long long #define ui unsigned int #define sh short #define LD long double #define lson (pos<<1) #define rson (pos<<1|1) #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define x1 lylakioi #define y1 gczakioi #define lb(x) (x&(-x)) #define hb(x) ((int)(__lg(x))) #define popcnt __builtin_popcount #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define inv(u) int I=ls[u],v=son[I];I<=rs[u];++I,v=son[I] #define psu pair<sh,ui> // #pragma gcc optimize(2) int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} string reads(){string res=".";char c=getchar();while(c<'a'||c>'z')c=getchar();while(c>='a'&&c<='z')res=res+c,c=getchar();return res;} void write(int x){if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');} const int MAXN=2050,MAXM=1200010,N=14,M=26,Mod=1e9+7,Mod2=1011451423; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,q,ps,a[MAXN]; ui p[MAXM]; char s[MAXM]; struct node{ int x,y; node operator+(const node&G){return {x+G.x>=Mod?x+G.x-Mod:x+G.x,y+G.y>=Mod2?y+G.y-Mod2:y+G.y};} node operator-(const node&G){return {x-G.x<0?x-G.x+Mod:x-G.x,y-G.y<0?y-G.y+Mod2:y-G.y};} node operator*(const node&G){return (node){(int)((ll)x*G.x%Mod),(int)((ll)y*G.y%Mod2)};} bool operator==(const node&G){return x==G.x&&y==G.y;} bool operator<(const node&G)const{return x!=G.x?x<G.x:y<G.y;} }B,ht[MAXN],jc[MAXN]; node qry(int l,int r){return ht[r]-ht[l-1]*jc[r-l+1];} map<node,pii>mp; int cnt=1; struct ACAM{ int _t[MAXN][M],f[MAXN]; ui num[MAXN]; void insert(int l,int r){ int pos=1; for(int i=l;i<=r;i++){ if(!_t[pos][s[i]-'a'])_t[pos][s[i]-'a']=++cnt; pos=_t[pos][s[i]-'a']; } num[pos]++; } queue<int>Q; void dfs(int u,int lst){ for(inx(u))if(v!=lst)num[v]+=num[u],dfs(v,u); } void build(){ for(int i=0;i<M;i++)_t[0][i]=1; Q.push(1); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=0;i<M;i++){ int v=_t[u][i]; if(!v)_t[u][i]=_t[f[u]][i]; else f[v]=_t[f[u]][i],add_side(v,f[v]),Q.push(v); } } dfs(1,1); // for(int i=1;i<=cnt;i++){ // cout<<i<<":"; // for(int j=0;j<M;j++)cout<<_t[i][j]<<" "; // cout<<" "<<num[i]<<" "<<f[i]<<endl; // } } psu to(int x,char c){return mk(_t[x][c-'a'],num[_t[x][c-'a']]);} }T; struct catree{ psu t[N][MAXN][MAXN]; int lg2[MAXN]; void build(int l,int r,int o){ if(!o){for(int i=2;i<=r;i++)lg2[i]=lg2[i>>1]+1;} if(l+1==r){ for(int i=1;i<=cnt;i++)t[o][l][i]=T.to(i,s[l]),t[o][r][i]=T.to(i,s[r]); return; } int mid=(l+r)>>1; build(l,mid,o+1),build(mid+1,r,o+1); for(int j=1;j<=cnt;j++)t[o][mid][j]=T.to(j,s[mid]); for(int i=mid-1;i>=l;i--) for(int j=1;j<=cnt;j++)t[o][i][j]=t[o][i+1][T.to(j,s[i]).fr],t[o][i][j].sc+=T.to(j,s[i]).sc; for(int j=1;j<=cnt;j++)t[o][mid+1][j]=T.to(j,s[mid+1]); for(int i=mid+2;i<=r;i++) for(int j=1;j<=cnt;j++)t[o][i][j]=T.to(t[o][i-1][j].fr,s[i]),t[o][i][j].sc+=t[o][i-1][j].sc; // cout<<l<<" "<<r<<" "<<o<<endl; // for(int i=l;i<=r;i++)cout<<t[o][i][1].fr<<" ";cout<<endl; } psu qry(int l,int r,int x){ int o=ps-1-lg2[l^r]; if(l==r)return t[o][l][x]; // cout<<l<<" "<<r<<" "<<o<<" "<<x<<" "<<t[o][l][x].fr<<" "<<t[o][r][t[o][l][x].fr].fr<<endl; return mk(t[o][r][t[o][l][x].fr].fr,t[o][r][t[o][l][x].fr].sc+t[o][l][x].sc); } }C; vector<pii>G[MAXM]; void slv(){B={131,127}; n=read(),m=read(),q=read(); for(int i=1;i<=n;i++){ scanf("%s",s+a[i-1]+1); a[i]=strlen(s+1); T.insert(a[i-1]+1,a[i]); for(int l=a[i-1]+1;l<=a[i];l++){ node hs={0,0}; for(int r=l;r<=a[i];r++)hs=hs*B+(node){s[r],s[r]},mp[hs]=mk(l,r); } } for(int i=n+1;i<=n+M;i++){ a[i]=a[i-1]+1; s[a[i]]=i-n-1+'a'; T.insert(a[i-1]+1,a[i]); for(int l=a[i-1]+1;l<=a[i];l++){ node hs={0,0}; for(int r=l;r<=a[i];r++)hs=hs*B+(node){s[r],s[r]},mp[hs]=mk(l,r); } } n+=M; ht[0]={0,0},jc[0]={1,1}; for(int i=1;i<=a[n];i++)ht[i]=ht[i-1]*B+(node){s[i],s[i]},jc[i]=jc[i-1]*B; T.build(); ps=0; while((1<<ps)<=a[n])ps++; // cout<<ps<<endl; s[0]='a'; for(int i=a[n]+1;i<1<<ps;i++)s[i]='a'; C.build(0,(1<<ps)-1,0); for(int i=1;i<=m;i++){ scanf("%s",s+1); int x=strlen(s+1); p[i]=-x; node hs={0,0}; for(int o=1;o<=x;o++){ // cout<<"bg"<<endl; node tmp=hs; hs=hs*B+(node){s[o],s[o]}; // cout<<"ed"<<" "<<hs.x<<" "<<hs.y<<" "<<mp[tmp].fr<<" "<<mp[tmp].sc<<" "<<mp.count(hs)<<" "<<G[i].size()<<endl; if(!mp.count(hs))G[i].pb(mp[tmp]),hs=(node){s[o],s[o]}; } G[i].pb(mp[hs]); int pos=1; for(auto o:G[i]){ psu tmp=C.qry(o.fr,o.sc,pos); p[i]+=tmp.sc,pos=tmp.fr; // cout<<o.fr<<","<<o.sc<<" "; // cout<<o.fr<<" "<<o.sc<<" "<<tmp.sc<<" "<<pos<<endl; } // cout<<endl; // cout<<"!!!"<<endl; if(G[i].size()>4){ swap(G[i][2],G[i][G[i].size()-2]),swap(G[i][3],G[i][G[i].size()-1]); while(G[i].size()>4)G[i].pop_back(); } // for(auto w:G[i])cout<<w.fr<<","<<w.sc<<" ";cout<<endl; } for(int o=m+1;o<=m+q;o++){ int x=read(),y=read(); p[o]=p[x]+p[y]; int pos=1; for(int i=max(0,(int)G[x].size()-2);i<G[x].size();i++)pos=C.qry(G[x][i].fr,G[x][i].sc,pos).fr; for(int i=0;i<min(2,(int)G[y].size());i++){ psu tmp=C.qry(G[y][i].fr,G[y][i].sc,pos); p[o]+=tmp.sc,pos=tmp.fr; } pos=1; for(int i=0;i<min(2,(int)G[y].size());i++){ psu tmp=C.qry(G[y][i].fr,G[y][i].sc,pos); p[o]-=tmp.sc,pos=tmp.fr; } for(auto w:G[x])G[o].pb(w); bool fl=0; for(auto w:G[y])if(!fl){ node tmp=qry(G[o].back().fr,G[o].back().sc)*jc[w.sc-w.fr+1]+qry(w.fr,w.sc); if(mp.count(tmp))G[o].pop_back(),G[o].pb(mp[tmp]); else G[o].pb(w),fl=1; }else G[o].pb(w); if(G[o].size()>4){ swap(G[o][2],G[o][G[o].size()-2]),swap(G[o][3],G[o][G[o].size()-1]); while(G[o].size()>4)G[o].pop_back(); } // for(auto w:G[o]){ // for(int i=w.fr;i<=w.sc;i++)cout<<((char)qry(i,i).x); // cout<<" "; // } // cout<<endl; } for(int i=1;i<=m+q;i++)printf("%u\n",p[i]); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); // int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }