#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
#define int long long
const int N=6e5+50;
const int B=400;
const ll Mod=(1ll<<61)-1;

signed ch[N][26];
int Len[N],par[N],pos[N],tot=1,End;
void Extend(int c) {
    if(ch[End][c]) {
        int p=End,x=ch[p][c];
        if(Len[p]+1==Len[x]) End=x;
        else {
            int y=++tot;Len[y]=Len[p]+1;
            memcpy(ch[y],ch[x],sizeof(ch[x]));
            par[y]=par[x];End=par[x]=y;
            for(; ch[p][c]==x; p=par[p]) ch[p][c]=y;
        }
        return ;
    }
    int p=End;End=++tot;Len[End]=Len[p]+1;pos[End]=Len[End];
    for(; p && !ch[p][c]; p=par[p]) ch[p][c]=End;
    if(!p) par[End]=1;
    else {
        int x=ch[p][c];
        if(Len[p]+1==Len[x]) par[End]=x;
        else {
            int y=++tot;Len[y]=Len[p]+1;
            memcpy(ch[y],ch[x],sizeof(ch[x]));
            par[y]=par[x];par[End]=par[x]=y;
            for(; ch[p][c]==x; p=par[p]) ch[p][c]=y;
        }
    }
}
vector<int> E[N];
ll val[N];
void dfs(int x) {
    for(auto y: E[x]) {
        val[y]+=val[x];
        dfs(y);
        if(!pos[x]) pos[x]=pos[y];
    }
}
char S[N],T[N];
__int128 h[2][N];
__int128 pw[N];
ll ha(int e,int l,int r) {
    return ((h[e][r]-h[e][l-1]*pw[r-l+1])%Mod+Mod)%Mod;
}
signed tr[N][26];
ll ans[N];
vector<tuple<int,int,int>> G[N];
int mx[N];
ll sum[N];
int a[N];

ll pre_val(int l,int r) { 
    return sum[min(mx[l],r-l+1)];
}
ll suf_val(int p,int l) {
    if(l==Len[p]) return val[p];
    else return val[par[p]];
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    cin >> S+1 >> T+1;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) sum[i]=sum[i-1]+a[i];
    pw[0]=1;
    FOR(i,1,n) pw[i]=pw[i-1]*233%Mod;
    FOR(i,1,n) h[0][i]=(h[0][i-1]*233+S[i])%Mod;
    FOR(i,1,n) h[1][i]=(h[1][i-1]*233+T[i])%Mod;
    FOR(i,1,n) {
        int l=1,r=n-i+1;
        while(l<=r) {
            int mid=l+r>>1;
            if(ha(0,1,mid)==ha(1,i,i+mid-1)) mx[i]=mid,l=mid+1;
            else r=mid-1;
        }
    }
    End=1;
    FOR(i,1,n) Extend(T[i]-'a');
    End=1;
    FOR(i,1,n) Extend(S[i]-'a');
    FOR(i,2,tot) E[par[i]].push_back(i);

    int p=1;
    FOR(i,1,n) {
        p=ch[p][S[i]-'a'];
        val[p]+=a[i];
        // cerr << p << ' ' << a[i] << endl;
    }

    dfs(1);
    FOR(i,2,tot) {
        int e=pos[i]-Len[par[i]];
        if(e>=1 && e<=n) {
            tr[par[i]][T[e]-'a']=i;
        }
    }

    FOR(i,1,m) {
        int l,r;
        cin >> l >> r;
        G[l/B].push_back({r,l,i});
    }
    // cerr << par[6] << ' ' << par[4] << ' ' << par[20] << ' ' << par[2] << endl;
    // cerr << Len[6] << ' ' << Len[4] << ' ' << Len[20] << ' ' << Len[2] << endl;
    // cerr << val[6] << ' ' << val[4] << ' ' << val[20] << ' ' << val[2] << endl;
    FOR(i,0,n/B) {
        sort(G[i].begin(),G[i].end());
        if(G[i].size()==0) continue;
        auto [r,l,_]=G[i][0];
        ll s=0;
        int p=1;
        FOR(j,l,r) {
            p=ch[p][T[j]-'a'];
            s+=suf_val(p,j-l+1);
            // if(j==7) cerr << p << endl;
            // cerr << suf_val(p,r-l+1) << endl;
        }
        for(auto [nr,nl,id]: G[i]) {
            while(r<nr) {
                ++r;
                p=ch[p][T[r]-'a'];
                s+=suf_val(p,r-l+1);
            }
            while(nl<l) {
                --l;
                s+=pre_val(l,r);
                if(r-l+1>Len[p]) p=tr[p][T[l]-'a'];
            }
            while(nl>l) {
                s-=pre_val(l,r);
                ++l;
                if(r-l+1==Len[par[p]]) p=par[p];
            }
            ans[id]=s;
        }
    }
    FOR(i,1,m) cout << ans[i] << '\n';
    return 0;
}