//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
//#include <unordered_map>
//#include <unordered_set>
#include <cassert>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <atcoder/convolution>
//#include <atcoder/lazysegtree>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/segtree>
//#include <atcoder/string>
using namespace std;
//using namespace atcoder;
#define int long long
//#define L __int128
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define a first
#define b second
#define fi first
#define sc second
#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,x) for(int i=0;i<x;i++)
#define gnr(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define per(i,b) gnr(i,0,b)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
#define si(x) (int)(x.size())
#define pcnt(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()

#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
 
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
 
template<class t> using vc=vector<t>;
 
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.fi<<","<<p.sc<<"}";
}
 
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
 
 //https://codeforces.com/blog/entry/62393
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	//don't make x negative!
	size_t operator()(pair<int,int> x)const{
		return operator()(uint64_t(x.first)<<32|x.second);
	}
};
//unordered_set -> dtype, null_type
//unordered_map -> dtype(key), dtype(value)
using namespace __gnu_pbds;
template<class t,class u>
using hash_table=gp_hash_table<t,u,custom_hash>;

template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 998244353;
//const ll mod = 1000000007;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

struct mint{
	ll v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(ll vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint &operator+=(const mint&rhs){return s(v+rhs.v);}
	mint &operator-=(const mint&rhs){return s(v+mod-rhs.v);}
	mint &operator*=(const mint&rhs){v=ll(v)*rhs.v%mod;return *this;}
	mint &operator/=(const mint&rhs){return *this*=rhs.inv();}
	mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
	mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
	mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
	mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	friend mint operator+(ll x,const mint&y){
		return mint(x)+y;
	}
	friend mint operator-(ll x,const mint&y){
		return mint(x)-y;
	}
	friend mint operator*(ll x,const mint&y){
		return mint(x)*y;
	}
	friend mint operator/(ll x,const mint&y){
		return mint(x)/y;
	}
	friend ostream& operator<<(ostream&os,const mint&m){
		return os<<m.v;
	}
	friend istream& operator>>(istream&is,mint&m){
		ll x;is>>x;
		m=mint(x);
		return is;
	}
	bool operator<(const mint&r)const{return v<r.v;}
	bool operator==(const mint&r)const{return v==r.v;}
	bool operator!=(const mint&r)const{return v!=r.v;}
	explicit operator bool()const{
		return v;
	}
};
ll modpow(ll x,ll n,ll _md=mod){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%_md;
		x=x*x%_md;
		n>>=1;
	}
	return res;
}
#define _sz 1
mint F[_sz],R[_sz];
void make(){
	F[0] = 1;
	for(int i=1;i<_sz;i++) F[i] = F[i-1] * i;
	R[_sz-1] = F[_sz-1].pow(mod-2);
	for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1);
}
mint C(int a,int b){
	if(b < 0 || a < b) return mint();
	return F[a]*R[b]*R[a-b];
}
using ld=long double;
using vi=vc<int>;
using ull=unsigned long long;
/*int dst(P p, P q){
	return (p.a-q.a)*(p.a-q.a)+(p.b-q.b)*(p.b-q.b);
}*/
/*template<class t>
void add_inplace(t &a, t b){
	if(a.size() < b.size()) swap(a, b);
	for(int i=0;i<si(b);i++){
		a[i] += b[i];
		if(a[i] < 0) a[i] += mod;
		if(a[i] >= mod) a[i] -= mod;
	}
	return ;
}*/
template<class t>
void ov(const vc<t>&a){
	if(a.empty()) return;
	rep(i, si(a)) cout << a[i] << (i+1==si(a)?'\n':' ');
}
//o(ans?"Yes":"No");
//from maroon library
//O(N+max(A)) なので座標圧縮してから動かしてください
//Verify yosupo (N=500000,string,43ms)
template<class t>vi sais(t a){
	int n=si(a),m=*max_element(all(a))+1;
	vi pos(m+1),x(m),sa(n),val(n),lms;
	for(auto c:a)pos[c+1]++;
	rep(i,m)pos[i+1]+=pos[i];
	vc<bool> s(n);
	per(i,n-1)s[i]=a[i]!=a[i+1]?a[i]<a[i+1]:s[i+1];
	auto ind=[&](const vi&ls){
		fill(all(sa),-1);
		auto L=[&](int i){if(i>=0&&!s[i])sa[x[a[i]]++]=i;};
		auto S=[&](int i){if(i>=0&& s[i])sa[--x[a[i]]]=i;};
		rep(i,m)x[i]=pos[i+1];
		per(i,si(ls))S(ls[i]);
		rep(i,m)x[i]=pos[i];
		L(n-1);
		rep(i,n)L(sa[i]-1);
		rep(i,m)x[i]=pos[i+1];
		per(i,n)S(sa[i]-1);
	};
	auto ok=[&](int i){return i==n||(!s[i-1]&&s[i]);};
	auto same=[&](int i,int j){
		do{
			if(a[i++]!=a[j++])return false;
		}while(!ok(i)&&!ok(j));
		return ok(i)&&ok(j);
	};
	rng(i,1,n)if(ok(i))lms.pb(i);
	ind(lms);
	if(si(lms)){
		int p=-1,w=0;
		for(auto v:sa)if(v&&ok(v)){
			if(p!=-1&&same(p,v))w--;
			val[p=v]=w++;
		}
		vi b=lms;
		for(auto&v:b)v=val[v];
		b=sais(b);
		for(auto&v:b)v=lms[v];
		ind(b);
	}
	return sa;
}
//string basics
//t is string or vi (int or ll?)
template<class t>
struct SB{
	vi rw, sa, ran, lcp, z;
	vc<vc<P>>bin;
	vc<int>look;
	//Turn on when TL is tight
	bool linear_only=false;
	SB(t a){
		int n=si(a);
		vi za;
		rw.assign(n, 0);
		za.assign(n, 0);
		int _mx_a = 0;
		rep(i, n){
			rw[i] = (int)a[i];
			za[i] = (int)a[i];
			chmax(_mx_a, rw[i]);
		}
		if(n*10 < _mx_a){
			SORT(za); ERASE(za);
			rep(i, n) rw[i] = POSL(za, rw[i]);
		}
		sa = sais(rw);
		ran.assign(n, 0);
		for(int i=0;i<n;i++) ran[sa[i]] = i;
		int h=0;
		lcp.assign(n, 0);
		rep(i,n){
			if(h) h--;
			if(!ran[i]) {
				h=0;continue;
			}
			int j = sa[ran[i]-1];
			while(j+h<n and i+h<n){
				if(a[j+h] != a[i+h]) break;
				h++;
			}
			lcp[ran[i]-1] = h;
		}
		z.assign(n, 0);
		z[0] = n;
		int _i=1, _j=0;
		while(_i<n){
			while(_i+_j<n and a[_j]==a[_i+_j]) _j++;
			z[_i] = _j;
			if(!_j){
				_i++;
				continue;
			}
			int k = 1;
			while(_i+k<n and k+z[k]<_j) z[_i+k]=z[k],++k;
			_i+=k; _j-=k;
		}
		if(linear_only or n<=1) return;
		int mx=0;
		while((1<<mx)<n) mx++;
		bin.assign(mx, vc<P>(n-1, P(-1, -1)));
		rep(i, n-1) bin[0][i] = P(lcp[i], i);
		rep(j, mx-1){
			rep(i, n-1){
				if(i+(1<<j) >= n-1) bin[j+1][i] = bin[j][i];
				else bin[j+1][i] = min(bin[j][i], bin[j][i+(1<<j)]);
			}
		}
		look.assign(n, 0);
		rng(i, 1, n) {
			look[i] = look[i-1];
			while(i > (2<<look[i])) look[i]++;
		}
	}
	//get lcp of S[sa[a]:], ..., S[sa[b]:]
	P get_by_ran(int a, int b){
		//assume 0<=a<b<n
		int len=b-a;
		return min(bin[look[len]][a], bin[look[len]][b-(1<<look[len])]);
	}
	//get_by_pos lcp of S[a:] and S[b:]
	P get(int a, int b){
		//assume 0<=a,b<n and a!=b
		a=ran[a],b=ran[b];
		if(a > b) swap(a, b);
		return get_by_ran(a, b);
	}
	//child id, length, one of starting pos and current pos
	using ei=vc<tuple<int,int,int,int>>;
	//edge information and terminal nodes of all suffixes
	pair<vc<ei>, vi> suftree(){
		if(rw.empty()) return mp(vc<ei>(), vi());
		if(rw.size()==1){
			vc<ei>ret(2);
			ret[0].eb(1, 1, 0, 0);
			vi ret2{1};
			return mp(ret, ret2);
		}
		int n=si(rw);
		vc<ei> edge; edge.reserve(2*n); edge.pb(ei());
		vi goal; goal.assign(n, -1);
		
		int nxt=1, cur=0;
		auto A = get_by_ran(0, n-1);
		if(A.a > 0){
			//exception
			//all same: aaaa...a
			assert(A.a == 1);
			edge[0].eb(1, A.a, 0, 0);
			edge.pb(ei()); nxt++; cur++; 
		}
		
		auto dfs=[&](auto self, int id, int lb, int ub, int cdep)->void{
			//[lb, ub], id=id
			while(1){
				int cut=ub;
				if(lb < ub){
					auto curmin = get_by_ran(lb, ub);
					if(curmin.a == cdep) cut = curmin.b;
				}
				if(lb == cut){
					if(n-sa[lb] == cdep){
						goal[sa[lb]] = id;
					}
					else{
						edge[id].eb(nxt, n-sa[lb]-cdep, sa[lb], sa[lb]+cdep);
						goal[sa[lb]] = nxt;
						edge.pb(ei()); nxt++;
					}
				}
				else{
					auto nxtmin = get_by_ran(lb, cut);
					edge[id].eb(nxt, nxtmin.a-cdep, sa[lb], sa[lb]+cdep);
					edge.pb(ei()); nxt++;
					self(self, nxt-1, lb, cut, nxtmin.a);
				}
				lb = cut+1;
				if(lb > ub) break;
			}
		};
		dfs(dfs, cur, 0, n-1, A.a);
		return mp(edge,goal);
	}
};
struct BIT_sum
{
	vi bit;
	void init(int sz){
		bit.clear();
		bit.assign(sz+3, 0);
	}
	void add(int i,int x)
	{
		i++;
		for(int s=i;s<si(bit);s+=s&-s) bit[s]+=x;
	}
	int sum(int i)
	{
		i++;
		int res=0;
		for(int s=i;s>0;s-=s&-s) res+=bit[s];
		return res;
	}
}bs;
struct BIT_min
{
	vi bit;
	void init(int sz){
		bit.clear();
		bit.assign(sz+3, INF);
	}
	void add(int i,int x)
	{
		i++;
		for(int s=i;s<si(bit);s+=s&-s) chmin(bit[s],x);
	}
	int sum(int i)
	{
		i++;
		int res=INF;
		for(int s=i;s>0;s-=s&-s) chmin(res,bit[s]);
		return res;
	}
}bm;
#define Z_SZ 300005
int A[Z_SZ];
template<class t>
void Z(t S){
	A[0] = S.size();
	int i=1,j=0;
	while(i<S.size()){
		while(i+j<S.size() && S[j]==S[i+j])j++;
		A[i]=j;
		if(j==0){
			i++; continue;
		}
		int k = 1;
		while(i+k<S.size() && k+A[k]<j) A[i+k]=A[k],++k;
		i+=k;j-=k;
	}
}
//A is MP
//B is KMP
struct KMP{
	vector<int>A,B,S;
	int j ;
	void init(int sz){
		A.resize(sz,0);
		B.resize(sz,0);
		S.resize(sz,0);
		A[0] = -1;
		B[0] = -1;
	}
	void update(int pos,int val){
		S[pos] = val;
	}
	void make_MP(int pos){
		j = A[pos];
		while(j >= 0 && S[pos] != S[j]) j = A[j];
		
		j++;
		A[pos+1] = j;
	}
	void make_KMP(int pos){
		j = A[pos];
		while(j >= 0 && S[pos] != S[j]) j = A[j];
		
		j++;
		if(S[pos+1] == S[j]) B[pos+1] = B[j];
		else B[pos+1] =  j;
	}
	//[i...pos]はprefixに等しく
	//[i+1...pos]はprefixに等しくならないようなiに対して、pos-i+1をまとめて返す
	//オフラインならZ algoと同じ結果になる、はず
	//verify CF612 E
	vector<int>get_len(int pos){
		int nxt = S[pos+1];
		vector<int>ret;
		pos = B[pos+1];
		
		while(pos > 0){
			ret.pb(pos);
			pos = A[pos];
			if(pos <= 0) break;
			if(S[pos] == nxt) pos = B[pos];
		}
		
		return ret;
	}
}kmp;
int n,m;
string s,t;
int w[150005],ans[150005],rui[150005],dp[150005];
vc<P>q[150005];
void solve(){
	cin>>n>>m;
	cin>>s>>t;
	repn(i,n){
		cin>>w[i];
		rui[i]=rui[i-1]+w[i];
	}
	string qs = s+"#"+t;
	Z(qs);
	kmp.init(si(s)+5);
	rep(i,si(s)) kmp.update(i,s[i]-'a');
	rep(i,si(s)){
		kmp.make_MP(i);
		dp[i+1] = rui[i+1];
		dp[i+1] += dp[kmp.A[i+1]];
	}
	rep(i,m){
		int l,r;cin>>l>>r;
		q[l].eb(r,i);
	}
	bs.init(n);
	bm.init(n);
	for(int i=n;i>=1;i--){
		int x = A[si(s)+i];
		//cout<<x<<endl;
		if(x){
			bs.add(i+x-1, rui[x]); //cout<<i+x-1<<" "<<rui[x]<<endl;
			bm.add(n+1-(i+x-1), i);
		}
		for(auto [r,id]:q[i]){
			ans[id] += bs.sum(r-1);
			//cout<<i<<" "<<r<<" "<<ans[id]<<endl;
			int x = bm.sum(n+1-r);
			//cout<<i<<" "<<r<<" "<<x<<endl;
			if(x <= r){
				ans[id] += dp[r-x+1];
			}
		}
	}
	rep(i,m) o(ans[i]);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t = 1; //cin >> t;
	while(t--) solve();
}