//蒟蒻一枚 rp++
//即得易见平凡，仿照上例显然。留作习题答案略，读者自证不难
//反之亦然同理，推论自然成立，略去过程Q.E.D.，由上可知证毕
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define re register
#define il inline
#define gc() getchar()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define tep(i,x) for(int i=head[x];~i;i=ne[i])
#define ls(x) x<<1
#define rs(x) x<<1|1
#define eps (1e-9)
#define inf 0x3f3f3f3f
#define INF 1e16
#define pii pair<int,int>
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define fi first
#define sc second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef double db;
namespace IO{
	template<typename T> inline void read(T &x){
		bool f=1;x=0;char ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=gc();
		x=f?x:-x;
	}
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
	   	if(x>9) write(x/10);
	   	putchar(char('0'+x%10));
	}
	template <typename T,typename ...Args> inline
	void read(T &x,Args &...args){read(x);read(args...);}
	template<typename T> inline void write(T x,char c){write(x),putchar(c);}
}
using namespace IO;
//bool _ST;
const int N=1.5e5+100;
int n,q,bd[N],z[N],lcp[N];
vector<pii> que[N];
LL sw[N],ans[N],sr[N];
char S[N],T[N];
void Z_function(){
	int l=0,r=0;z[1]=n;
	rep(i,2,n){
		if(r>=i) z[i]=min(z[i-l+1],r-i+1);
		while(S[i+z[i]]==S[1+z[i]]) ++z[i];
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
	l=r=0;
	rep(i,1,n){
		if(r>=i) lcp[i]=min(z[i-l+1],r-i+1);
		while(T[i+lcp[i]]==S[1+lcp[i]]) ++lcp[i];
		if(i+lcp[i]-1>r) l=i,i+lcp[i]-1;
	}
}
void border(){
	bd[0]=bd[1]=0;
	int k=0;
	sr[1]=sw[1];
	rep(i,2,n){
		while(k&&S[i]!=S[k+1]) k=bd[k];
		bd[i]=(S[i]!=S[k+1])?++k:k;
		sr[i]=sr[bd[i]]+sw[i];
	}
}
#define lowbit(u) (u&(-u))
struct BIT1{
	LL c[N];
	void update(int u,LL x){for(;u<=n+1;u+=lowbit(u)) c[u]+=x;}
	LL query(int u){LL res=0;for(;u;u-=lowbit(u)) res+=c[u];return res;}
}TR1;
struct SGT{
	int mn[N*9];
	SGT(){memset(mn,0x3f,sizeof mn);}
	void update(int x,int l,int r,int u,int v){
		mn[x]=min(mn[x],v);
		if(l==r) return;
		int mid=l+r>>1;
		if(mid>=u) update(ls(x),l,mid,u,v);
		else update(rs(x),mid+1,r,u,v);
 	}
 	int query(int x,int l,int r,int L,int R){
 		if(L<=l&&r<=R) return mn[x];
 		int mid=l+r>>1,res=inf;
 		if(mid>=L) res=query(ls(x),l,mid,L,R);
 		if(mid<R) res=min(res,query(rs(x),mid+1,r,L,R));
 		return res;
	}
}TR2;
//bool _ED;
signed main(){
	//fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	read(n,q);
	scanf("%s%s",(S+1),(T+1));
	rep(i,1,n) read(sw[i]),sw[i]+=sw[i-1];
	rep(i,1,q){
		int l,r;read(l,r);
		que[l].pb({r,i});
	}
	Z_function();
	border();
	per(i,n,1){
		if(i+lcp[i]<=n) TR1.update(lcp[i]+i,sw[lcp[i]]);
		TR2.update(1,1,n*2,lcp[i]+i,i);
		for(auto _:que[i]) {
			ans[_.sc]=TR1.query(_.fi);
			int pos=TR2.query(1,1,n*2,_.fi+1,n*2);
			if(pos<=_.fi) ans[_.sc]+=sr[_.fi-pos+1];
		}
	}
	rep(i,1,q) write(ans[i],'\n');
	//fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}
//谨记:
//十年OI一场空，不开longlong见祖宗
//数据千万条，清空第一条。多测不清空，爆零两行泪。清空不规范，TLE总相伴。
//快读要加类型名