#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 p1 = 1e9 + 7;
const int p2 = 998244353;
const int base1 = 137;
const int base2 = 131;
const int SIZE = 500;

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, int p){
    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;

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

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

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 int find(int u, int v){
    if(u <= v) return u;
    for(int i = 18; ~i; --i){
        if(ac[u][i] > v){
            u = ac[u][i];
        }
    }
    return ac[u][0];
}

inline void addr(int l, int r){
    int x = find(lenl[r], r - l + 1);
    // cerr << l << " " << r << " " << x << endl;
    if(x) ans += g[x];
}

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

inline void dell(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;
        while(l < R[x]+1) dell(l++, r);
        ans = t;
    }
}

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

int hashs1[N];
int hasht1[N];
int pw1[N];
int hashs2[N];
int hasht2[N];
int pw2[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];
    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);
        // cerr << g[i] << " ";
    }
    // cerr << endl;
    dfs(1, 0);
    pw1[0] = 1;
    pw2[0] = 1;
    for(int i = 1; i <= n; ++i){
        hashs1[i] = ((ll)hashs1[i - 1] * base1 + s[i]) % p1;
        hashs2[i] = ((ll)hashs2[i - 1] * base2 + s[i]) % p2;
        hasht1[i] = ((ll)hasht1[i - 1] * base1 + t[i]) % p1;
        hasht2[i] = ((ll)hasht2[i - 1] * base2 + t[i]) % p2;
        pw1[i] = (ll)pw1[i - 1] * base1 % p1;
        pw2[i] = (ll)pw2[i - 1] * base2 % p2;
    }
    for(int i = 1; i <= n; ++i){
        int l = i, r = n, ans = i - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(hashs1[mid - i + 1] == sub(hasht1[mid], (ll)hasht1[i - 1] * pw1[mid - i + 1] % p1, p1)
            && hashs2[mid - i + 1] == sub(hasht2[mid], (ll)hasht2[i - 1] * pw2[mid - i + 1] % p2, p2)){
                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;
        }
        // cerr << lenl[i] << " ";
    }
    // cerr << endl;
    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;
}