#include<bits/stdc++.h> using namespace std; #define int long long int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=30000010; int n,m,q,k,a[MAXN],fail[MAXN],ct[MAXN]; char s[MAXN],t[MAXN],c[MAXN]; void slv0(){ int len=0; for(int i=1;i<=k;i++){ for(int j=1;j<=a[i];j++)c[++len]=s[j]; } int ind=0; for(int i=1;i<m;i++){ while(ind&&t[ind+1]!=t[i+1])ind=fail[ind]; if(t[ind+1]==t[i+1])ind++; fail[i+1]=ind; } ind=0; for(int i=1;i<=len;i++){ while(ind&&t[ind+1]!=c[i])ind=fail[ind]; if(t[ind+1]==c[i])ind++; if(ind==m)ct[i-m+1]++,ind=fail[ind]; } for(int i=1;i<=len;i++)ct[i]+=ct[i-1]; while(q--){ int l=read(),r=read(); if(r-l+1<=m)printf("0\n"); else printf("%lld\n",ct[r-m+1]-ct[l-1]); } } void slv(){ scanf("%s",s+1);scanf("%s",t+1); n=strlen(s+1),m=strlen(t+1); k=read(); for(int i=1;i<=k;i++)a[i]=read(); q=read(); slv0(); } signed main(){ // freopen("youl.in","r",stdin);freopen("youl.out","w",stdout); slv(); return 0; }