#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T &x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N = 1.5e5 + 7;
const int p = 1e9 + 7;
const int base = 137;
const int SIZE = 400;

int be[N];
int L[N];
int R[N];

struct Query{
    int l, r, id;
    inline bool operator < (const Query &a) const{
        return be[l] == be[a.l] ? r < a.r: l < a.l;
    }
}Q[N];


inline int sub(int a, int b){
    return a - b < 0 ? a - b + p : a - b;
}

ll f[N];
ll g[N];
int lenl[N];
int lenr[N];
ll Ans[N];
ll ans;

int Lg[N];
int dep[N];
vector<int> son[N];
int ac[N][20];

void dfs(int x){
    for(int i = 1; ac[x][i] = ac[ac[x][i - 1]][i - 1]; ++i);
    for(auto &v: son[x]){
        ac[v][0] = x;
        dep[v] = dep[x] + 1;
        dfs(v);
    }
}

inline int find(int u, int v){
    if(u <= v) return u;
    for(int i = Lg[dep[u] - dep[v]] + 2; ~i; --i){
        if(ac[u][i] > v){
            u = ac[u][i];
        }
    }
    return ac[u][0];
}

inline ll solve(int l, int r){
    ll ret = 0;
    for(int i = l; i<=r; ++i){
        ret += f[min(r - i + 1, lenr[i])];
    }
    return ret;
}

inline void addr(int l, int r){
    ans += g[find(lenl[r], r - l + 1)];
}

inline void addl(int l, int r){
    ans += f[min(r - l + 1, lenr[l])];
}

inline void Get(int x, int &i){
    int l = R[x] + 1, r = R[x];
    for(ans = 0; be[Q[i].l] == x; ++i){
        if(be[Q[i].r] == x){
            Ans[Q[i].id] = solve(Q[i].l, Q[i].r);
            continue;
        }
        while(r < Q[i].r) addr(l, ++r);
        ll t = ans;
        while(l > Q[i].l) addl(--l, r);
        Ans[Q[i].id] = ans;
        l = R[x] + 1;
        ans = t;
    }
}

char s[N];
char t[N];
int w[N];
int Next[N];

int hashs[N];
int hasht[N];
int pw[N];

vector<int> ins[N];
vector<int> rem[N];

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int n, m; r(n), r(m);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    for(int i = 1; i <= n; ++i){
        r(w[i]);
        f[i] = f[i - 1] + w[i];
    }
    g[1] = w[1];
    son[0].push_back(1);
    for(int i = 2, j = 0; i <= n; ++i){
        while(s[j + 1] != s[i] && j) j = Next[j];
        if(s[j + 1] == s[i]) ++j;
        Next[i] = j;
        g[i] = w[i] + g[Next[i]];
        son[Next[i]].push_back(i);
    }
    dfs(0);
    pw[0] = 1;
    Lg[0] = -1;
    for(int i = 1; i <= n; ++i){
        hashs[i] = ((ll)hashs[i - 1] * base + s[i]) % p;
        hasht[i] = ((ll)hasht[i - 1] * base + t[i]) % p;
        pw[i] = (ll)pw[i - 1] * base % p;
        Lg[i] = Lg[i >> 1] + 1;
    }
    for(int i = 1; i <= n; ++i){
        int l = i, r = n, ans = i - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(hashs[mid - i + 1] == sub(hasht[mid], (ll)hasht[i - 1] * pw[mid - i + 1] % p)){
                l = mid + 1;
                ans = mid;
            }
            else{
                r = mid - 1;
            }
        }
        lenr[i] = ans - i + 1;
        if(lenr[i]){
            ins[i].push_back(i);
            rem[i + lenr[i]].push_back(i);
        }
    }
    multiset<int> S;
    for(int i = 1; i <= n; ++i){
        for(auto &x: ins[i]){
            S.insert(x);
        }
        for(auto &x: rem[i]){
            S.erase(S.find(x));
        }
        if(S.empty()){
            lenl[i] = 0;
        }
        else{
            lenl[i] = i - *S.begin() + 1;
        }
    }
    for(int i = 1; i <= n; ++i){
        be[i] = (i - 1) / SIZE + 1;
        if(!L[be[i]]) L[be[i]] = i;
        R[be[i]] = i;
    }
    for(int i = 1; i <= m; ++i){
        Q[i].id = i;
        r(Q[i].l), r(Q[i].r);
    }
    sort(Q + 1, Q + m + 1);
    for(int i = 1, x = 1; i <= m; ++x){
        Get(x, i);
    }
    for(int i = 1; i <= m; ++i){
        printf("%lld\n", Ans[i]);
    }
    return 0;
}