#include<bits/stdc++.h>
using namespace std;
int n,m,kmp[150100],is[150100],f[150100][20];
int z[150100],q[151000];
char s[150100],t[150100];
#define ll long long
ll w[151000],ds[150010];
int T[150100],cn,ls[10100000],rs[10100000];
ll su[10100000];
void up(int &p,int lst,int l,int r,int x,int z){
	p=++cn,su[p]=su[lst]+z,ls[p]=ls[lst],rs[p]=rs[lst];
	if(l==r)return;int mid=(l+r)>>1;
	if(x<=mid)up(ls[p],ls[lst],l,mid,x,z);
	else up(rs[p],rs[lst],mid+1,r,x,z);
}
ll ask(int p,int l,int r,int x){
	if(l==r)return su[p];
	int mid=(l+r)>>1;
	if(x<=mid)return ask(ls[p],l,mid,x);
	return su[ls[p]]+ask(rs[p],mid+1,r,x);
}
int main(){
	scanf("%d%d%s%s",&n,&m,s+1,t+1);
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[j+1]!=s[i])j=kmp[j];
		if(s[j+1]==s[i])j++;kmp[i]=j,f[i][0]=j;
	}
	z[1]=n;
	for(int i=2,j=0,mr=0;i<=n;i++){
		if(i<=mr)z[i]=min(mr-i+1,z[i-j+1]);
		while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]])z[i]++; 
		if(i+z[i]-1>mr)j=i,mr=i+z[i]-1;
	}
	for(int i=1,j=0,mr=0;i<=n;i++){
		if(i<=mr)q[i]=min(mr-i+1,z[i-j+1]);
		while(i+q[i]<=n&&s[1+q[i]]==t[i+q[i]])q[i]++;
		if(i+q[i]-1>mr)j=i,mr=i+q[i]-1;
	}
	for(int j=1;j<20;j++)for(int i=1;i<=n;i++){
		if(!f[i][j-1])f[i][j]=0;
		else f[i][j]=f[f[i][j-1]][j-1];
	}
	for(int i=1,j=0;i<=n;i++){
		scanf("%lld",&w[i]);w[i]+=w[i-1];
		while(j&&s[j+1]!=t[i])j=kmp[j];
		if(s[j+1]==t[i])j++;is[i]=j;
	}
	for(int i=1;i<=n;i++)ds[i]=ds[kmp[i]]+w[i];
	for(int i=n;i;i--){
		T[i]=T[i+1];
		if(q[i]&&i+q[i]<=n)up(T[i],T[i],1,n,i+q[i],w[q[i]]);
	}
	for(int i=1,l,r;i<=m;i++){
		scanf("%d%d",&l,&r);
		ll an=ask(T[l],1,n,r);
		//for(int j=l;j<=r;j++)if(j+q[j]-1<r)an+=w[q[j]];
		int u=is[r];
		if(u>r-l+1){
			for(int j=19;j>=0;j--)
			if(f[u][j]>r-l+1)u=f[u][j];
			u=kmp[u];
		}
		an+=ds[u];
		printf("%lld\n",an);
	}
	return 0;
}