#include<bits/stdc++.h>
using namespace std;
#define MAXN 150005
#define ll long long
const ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;

int n, m, kmp[MAXN][20], lg[MAXN], dep[MAXN], mch[MAXN], len[MAXN];
ll val[MAXN], sum[MAXN], sum1[MAXN];
char s[MAXN], t[MAXN];
int l = 1, r = 0;

struct Node{
	ll h1, h2;
	Node() {h1 = h2 = 0;}
	Node(ll a, ll b) {h1 = (a%mod1+mod1)%mod1, h2 = (b%mod2+mod2)%mod2;}
} pw[MAXN], hs[MAXN], ht[MAXN];
Node operator+(const Node& a, const Node& b){
	return Node(a.h1+b.h1, a.h2+b.h2);
}
Node operator-(const Node& a, const Node& b){
	return Node(a.h1-b.h1, a.h2-b.h2);
}
Node operator*(const Node& a, const Node& b){
	return Node(a.h1*b.h1, a.h2*b.h2);
}
bool operator==(const Node& a, const Node& b){
	return a.h1 == b.h1 && a.h2 == b.h2;
}

Node sub(int l, int r) {return ht[r] - ht[l-1] * pw[r-l+1];}


int lcp(int x){
	int l = 1, r = n-x+1, mid, ans = 0;
	while(l <= r){
		mid = (l+r)>>1;
		if(sub(x, x+mid-1) == hs[mid]) ans = mid, l = mid+1;
		else r = mid-1;
	}
	return ans;
}

void init(){
	int j = 0;
	for(int i=1;i<=n;i++) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i);
	for(int i=2;i<=n;i++){
		while(j && s[j+1] != s[i]) j = kmp[j][0];
		if(s[j+1] == s[i]) j++;
		kmp[i][0] = j;
		if(j && !dep[j]){
			dep[j] = dep[kmp[j][0]] + 1;
			for(int k=1;k<lg[dep[j]];k++) kmp[j][k] = kmp[kmp[j][k-1]][k-1];
		}
	}
	for(int i=1;i<=n;i++) sum[i] = val[i] + sum[kmp[i][0]];
	for(int i=1;i<=n;i++) len[i] = lcp(i);
	for(int i=1;i<=n;i++) sum1[i] = sum1[i-1] + val[i];
	j = 0;
	for(int i=1;i<=n;i++){
		while(j && s[j+1] != t[i]) j = kmp[j][0];
		if(s[j+1] == t[i]) j++;
		mch[i] = j;
	}
	// for(int i=1;i<=n;i++) printf("kmp[%d] = %d\n", i, kmp[i][0]);
	// for(int i=1;i<=n;i++) printf("mch[%d] = %d, len = %d\n", i, mch[i], len[i]);
}

int siz, bcnt, belong[MAXN];
struct Query{
	int l, r, id;
} Q[MAXN];
bool cmp(const Query& a, const Query& b){
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void initMo(){
	siz = 1000;
	bcnt = ceil(double(n) / siz);
	for(int i=1;i<=bcnt;i++) for(int j=(i-1)*siz+1;j<=n&&j<=i*siz;j++) belong[j] = i;
}

ll ans[MAXN], now = 0;

void addL(){
	--l;
	int tmp = min(len[l], r-l+1);
	now += sum1[tmp];
}
void addR(){
	++r;
	int len = mch[r];
	if(len <= r-l+1) {now += sum[len]; return;}
	for(int i=lg[dep[len]]-1;i>=0;i--){
		if(kmp[len][i] > r-l+1) len = kmp[len][i];
	}
	len = kmp[len][0];
	now += sum[len];
}
void delL(){
	int tmp = min(len[l], r-l+1);
	now -= sum1[tmp];
	l++;
}
void delR(){
	int len = mch[r];
	if(len <= r-l+1) {now -= sum[len]; r--; return;}
	for(int i=lg[dep[len]]-1;i>=0;i--){
		if(kmp[len][i] > r-l+1) len = kmp[len][i];
	}
	len = kmp[len][0];
	now -= sum[len];
	r--;
}

int main(){
	cin>>n>>m; 
	pw[0] = {1, 1}, pw[1] = Node(1e4+7, 1e4+9);
	for(int i=2;i<=n;i++) pw[i] = pw[i-1] * pw[1];
	scanf("%s", s+1), scanf("%s", t+1);
	for(int i=1;i<=n;i++) scanf("%lld", &val[i]);
	for(int i=1;i<=n;i++) hs[i] = hs[i-1] * pw[1] + Node(s[i]-'a'+1, s[i]-'a'+1);
	for(int i=1;i<=n;i++) ht[i] = ht[i-1] * pw[1] + Node(t[i]-'a'+1, t[i]-'a'+1);
	init();
	initMo();
	// puts("-----------");
	for(int i=1;i<=m;i++) scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].id = i;
	sort(Q+1, Q+1+m, cmp);
	for(int i=1;i<=m;i++){
		int ql = Q[i].l, qr = Q[i].r;
		// printf("i = %d, ql = %d, qr = %d\n", i, ql, qr);
		while(l > ql) addL();
		// printf("l = %d, r = %d\n", l, r);/
		while(r < qr) addR();
		// printf("l = %d, r = %d\n", l, r);
		while(l < ql) delL();
		// printf("l = %d, r = %d\n", l, r);
		while(r > qr) delR();
		// printf("l = %d, r = %d\n", l, r);
		ans[Q[i].id] = now;
		// printf("l = %d, r = %d\n", l, r);
	}
	for(int i=1;i<=m;i++) printf("%lld\n", ans[i]);
	return 0;
}