#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 using namespace std; typedef long long ll; const int maxn=1e7+10; const int B1=59,B2=61,B3=127,M1=998244353,M2=1e9+7,M3=1011451423; 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,sm[maxn];string s,t; int pw1[maxn],pw2[maxn],pw3[maxn]; struct H { int s1,s2,s3,l; H(){s1=s2=s3=l=0;} H(int a,int b,int c,int d){s1=a,s2=b,s3=c,l=d;} }d[maxn]; H operator+(H a,H b){ H c; c.s1=(a.s1*1ll*pw1[b.l]%M1+b.s1)%M1; c.s2=(a.s2*1ll*pw2[b.l]%M2+b.s2)%M2; c.s3=(a.s3*1ll*pw3[b.l]%M3+b.s3)%M3; c.l=a.l+b.l;return c; } H operator-(H a,H b){ H c;c.l=a.l-b.l; c.s1=(a.s1-b.s1*1ll*pw1[c.l]%M1+M1)%M1; c.s2=(a.s2-b.s2*1ll*pw2[c.l]%M2+M2)%M2; c.s3=(a.s3-b.s3*1ll*pw3[c.l]%M3+M3)%M3; return c; } bool operator==(H a,H b){return (a.l==b.l&&a.s1==b.s1&&a.s2==b.s2&&a.s3==b.s3);} void gen(){ pw1[0]=pw2[0]=pw3[0]=1; int n=1e7;up(i,1,n)pw1[i]=pw1[i-1]*1ll*B1%M1,pw2[i]=pw2[i-1]*1ll*B2%M2,pw3[i]=pw3[i-1]*1ll*B3%M3; } void slv(){gen(); cin>>s>>t; string P=""; int n=read();up(i,1,n){int x=read();up(i,0,x-1)P.p_b(s[i]);} P=" "+P;H ht;for(char ch:t)ht=ht+H(ch-'a'+1,ch-'a'+1,ch-'a'+1,1); int sz=P.size()-1;up(i,1,sz)d[i]=d[i-1]+H(P[i]-'a'+1,P[i]-'a'+1,P[i]-'a'+1,1); up(i,1,sz-(int)t.size()+1)sm[i]=sm[i-1]+((d[i+(int)t.size()-1]-d[i-1])==ht); int q=read(); while(q--){ int l=read(),r=read()-(int)t.size()+1; if(l>r)printf("0\n"); else printf("%d\n",sm[r]-sm[l-1]); } }int main(){ //freopen("youl.in","r",stdin); //freopen("youl.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }