#include <bits/stdc++.h>
using namespace std;
struct T{array<int,4>n;int tin,tout;T(){n.fill(0);}};
int cv(char c){return c=='A'?0:c=='G'?1:c=='C'?2:3;}
void df(vector<T>&t,int u,int&c){t[u].tin=++c;for(int d=0;d<4;d++)if(t[u].n[d])df(t,t[u].n[d],c);t[u].tout=c;}
struct F{int x,l,r,s,i;};
struct B{int n;vector<int>t;B(int n):n(n),t(n+1){};void u(int i,int v){for(;i<=n;i+=i&-i)t[i]+=v;}int q(int i){int s=0;for(;i>0;i-=i&-i)s+=t[i];return s;}};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k,c,g;
cin>>n>>k>>c>>m;
vector<string>s(n);
for(int i=0;i<n;i++)cin>>s[i];
vector<string>p(m),q(m);
for(int i=0;i<m;i++)cin>>p[i]>>q[i];
vector<T>tp(1),tq(1);
for(int i=0;i<n;i++){
int u=0;
for(char ch:s[i]){
int d=cv(ch);
if(!tp[u].n[d]){tp[u].n[d]=tp.size();tp.emplace_back();}
u=tp[u].n[d];
}
}
for(int i=0;i<n;i++){
int u=0;
for(int j=s[i].size()-1;j>=0;j--){
int d=cv(s[i][j]);
if(!tq[u].n[d]){tq[u].n[d]=tq.size();tq.emplace_back();}
u=tq[u].n[d];
}
}
int cp=0,cs=0;
df(tp,0,cp);
df(tq,0,cs);
vector<pair<int,int>>v(n);
for(int i=0;i<n;i++){
int u=0;
for(char ch:s[i])u=tp[u].n[cv(ch)];
int x=tp[u].tin;
u=0;
for(int j=s[i].size()-1;j>=0;j--)u=tq[u].n[cv(s[i][j])];
int y=tq[u].tin;
v[i]={x,y};
}
vector<F>e;
for(int i=0;i<m;i++){
int u=0,l1,r1,l2,r2;
for(char ch:p[i]){
int d=cv(ch);
if(!tp[u].n[d]){u=-1;break;}
u=tp[u].n[d];
}
if(u<0)continue;
l1=tp[u].tin;r1=tp[u].tout;
u=0;
for(int j=q[i].size()-1;j>=0;j--){
int d=cv(q[i][j]);
if(!tq[u].n[d]){u=-1;break;}
u=tq[u].n[d];
}
if(u<0)continue;
l2=tq[u].tin;r2=tq[u].tout;
e.push_back({r1,l2,r2,1,i});
e.push_back({l1-1,l2,r2,-1,i});
}
sort(v.begin(),v.end());
sort(e.begin(),e.end(),[](auto&a,auto&b){return a.x<b.x;});
B b(cs);
vector<long long>ans(m);
int j=0;
for(auto&f:e){
while(j<n&&v[j].first<=f.x){
b.u(v[j].second,1);
j++;
}
int t=b.q(f.r)-b.q(f.l-1);
ans[f.i]+=f.s*(long long)t;
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
return 0;
}
