#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 len[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, len[i])];
    }
    return ret;
}

inline int find(int u, int dep){
    for(int i = 18; ~i; --i){
        if(ac[u][i] >= dep){
            u = ac[u][i];
        }
    }
    return u;
}

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

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

inline void dell(int l, int r){
    ans -= f[min(r - l + 1, len[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(r, --l);
        Ans[Q[i].id] = ans;
        while(l < R[x]+1) dell(r, l++);
        ans = t;
    }
}

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

int hashs[N];
int hasht[N];
int pw[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 <= m; ++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(1, 0);
    pw[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;
    }
    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;
            }
        }
        len[i] = ans - i + 1;
        // cerr << len[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;
}