#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=3e7+10; 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],tg[maxn];string s,t; int fail[maxn]; void kmp(){ int j=0,sz=t.size()-1; up(i,2,sz){ while(j&&t[j+1]!=t[i])j=fail[j]; if(t[j+1]==t[i])j++; fail[i]=j; }int tmp=sz; sz=s.size()-1;j=0; up(i,1,sz){ while(j&&t[j+1]!=s[i])j=fail[j]; if(t[j+1]==s[i])j++; if(j==tmp)tg[i-tmp+1]=1,j=fail[j]; } up(i,1,sz)sm[i]=sm[i-1]+tg[i]; } void slv(){ cin>>s>>t;t=" "+t; string P=" "; int n=read();up(i,1,n){int x=read();up(i,0,x-1)P.p_b(s[i]);} s=P;kmp(); int q=read(); while(q--){ int l=read(),r=read()-(int)(t.size()-1)+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; }