#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
char s[N],t[N];
long long ex[N],z[N];
int lens,lent;
int nxt[N];
int n,m;
void kmp_nxt(){
	nxt[0]=-1;
	nxt[1]=0;
	int k=0;
	for(int i=2;i<=n;i++){
		while(s[i]!=s[k+1]&&k>=0)k=nxt[k];
		nxt[i]=++k;
	}
}
void exkmp_nxt(){
	int maxpos=1,maxr=0;
	z[1]=lent;
	for(int i=2;i<=n;i++){
		if(i<=maxr)z[i]=min(maxr-i+1,z[i+1-maxpos]);
		else z[i]=0;
		while(i+z[i]<=n&&s[z[i]+i]==s[z[i]+1])z[i]++;
		if(i+z[i]-1>maxr){
			maxpos=i;
			maxr=i+z[i]-1;
		}
	}
}
void exkmp(){
	int maxpos=1,maxr=0;
	for(int i=1;i<=n;i++){
		if(i<=maxr)ex[i]=min(maxr-i+1,z[i+1-maxpos]);
		else ex[i]=0;
		while(i+ex[i]<=n&&t[ex[i]+i]==s[ex[i]+1])ex[i]++;
		if(i+ex[i]-1>maxr){
			maxpos=i;
			maxr=i+ex[i]-1;
		}
	}
}
int delta[N];
int c[N];
int ans[N],d[N];
int sc[N],ss[N];
int f[N][22],_log[N];
signed main(){
	cin>>n>>m;
	cin>>s+1>>t+1;
	kmp_nxt();
	exkmp_nxt();
	exkmp();
	for(int i=1;i<=n;i++){
		scanf("%lld",&c[i]);
		sc[i]=sc[i-1]+c[i];
	}
	for(int i=1;i<=n;i++){
		d[i]=c[i]+d[nxt[i]];
		ans[i]=ans[i-1]+d[i];
	}
	for(int i=1;i<=n;i++){
		ss[i]=ss[i-1]+sc[ex[i]];
		delta[i]=i+ex[i]-1;
		f[i][0]=delta[i];
		//cout<<ex[i]<<" ";
	}
	//cout<<"\n";
	_log[1]=0;
	for(int i=2;i<=n;i++){
		if(i==(1<<(_log[i-1]+1)))_log[i]=_log[i-1]+1;
		else _log[i]=_log[i-1];
	}
	/*for(int i=1;i<=n;i++){
		delta[i]=max(delta[i-1],delta[i]);
		cout<<delta[i]<<"\n";
	}*/
	for(int i=1;i<=_log[n];i++){
		for(int j=1;j<=n-(1<<i)+1;j++){
			f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		int noww=x;
		for(int j=_log[y-x+1];j>=0;j--){
			if(f[noww][j]<y)noww+=(1<<j);
		}
		
		if(noww<x)cout<<"??\n";
		if(y-noww+1<0)cout<<"!!\n";
		cout<<ans[y-noww+1]+ss[noww-1]-ss[x-1]<<"\n";//l~ans-1
		//t[ans~r]=s[1~r-ans+1]
	}
	return 0;
}