#include <bits/stdc++.h>
using namespace std;

#define fopen                                   \
    freopen("E:/vscode/oi/in.txt", "r", stdin); \
    freopen("E:/vscode/oi/out.txt", "w", stdout);
#define ios                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);

#define i64 long long
#define ull unsigned i64
#define pii pair<int, int>
#define pdd pair<double, double>
#define ld long double
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) (x & -x)
#define de(x) cout << #x << " = " << x << '\n'
#define MAXP 20

const int N = 1.5e5 + 10, M = 1e2 + 10;
const double eps = 1e-12;
const double PI = acos(-1);

bool Mst;

int rt[N], cnt;
struct tr1
{
    struct node
    {
        int ch[2];
        i64 s;
    } tr[N * 30];
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
    void modify(int x, int &y, int l, int r, int pos, i64 c)
    {
        y = ++cnt;
        tr[y] = tr[x];
        tr[y].s += c;
        if (l == r)
            return;
        int m = l + r >> 1;
        if (pos <= m)
            modify(lc(x), lc(y), l, m, pos, c);
        else
            modify(rc(x), rc(y), m + 1, r, pos, c);
    }

    i64 query(int x, int l, int r, int ql, int qr)
    {
        if (ql <= l && qr >= r)
            return tr[x].s;
        int m = l + r >> 1;
        i64 res = 0;
        if (ql <= m)
            res += query(lc(x), l, m, ql, qr);
        if (qr > m)
            res += query(rc(x), m + 1, r, ql, qr);
        return res;
    }
} tr1;

i64 w[N], sw[N], pre[N];
int fail[N];
vector<int> e[N];
char s[N], t[N];
int z[N], p[N];
struct node
{
    int maxv;
} tr[N << 2];

void build(int x, int l, int r)
{
    if (l == r)
    {
        tr[x].maxv = p[l] + l - 1;
        return;
    }
    int m = l + r >> 1;
    build(ls(x), l, m);
    build(rs(x), m + 1, r);
    tr[x].maxv = max(tr[ls(x)].maxv, tr[rs(x)].maxv);
}

int query(int x, int l, int r, int ql, int qr, int lim)
{
    if (tr[x].maxv < lim)
        return N;
    if (l == r)
        return l;
    int m = l + r >> 1;
    if (ql <= m)
    {
        int res = query(ls(x), l, m, ql, qr, lim);
        if (res < N)
            return res;
    }
    if (qr > m)
    {
        int res = query(rs(x), m + 1, r, ql, qr, lim);
        if (res < N)
            return res;
    }
    return N;
}

void Z()
{
    int n = strlen(s + 1), m = strlen(t + 1);
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++)
    {
        z[i] = i > r ? 0 : min(z[i - l + 1], r - i + 1);
        while (s[1 + z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
    for (int i = 1, l = 0, r = 0; i <= m; i++)
    {
        p[i] = i > r ? 0 : min(z[i - l + 1], r - i + 1);
        while (p[i] < n && s[1 + p[i]] == t[i + p[i]])
            ++p[i];
        if (i + p[i] - 1 > r)
        {
            l = i;
            r = i + p[i] - 1;
        }
    }
}

void solve()
{
    int n, q;
    cin >> n >> q;
    cin >> s + 1 >> t + 1;
    Z();
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i], sw[i] = sw[i - 1] + w[i];
        e[p[i] + i - 1].push_back(i);
        // cout << p[i] << " \n"[i == n];
    }
    for (int i = 1; i <= n; i++)
    {
        rt[i] = rt[i - 1];
        for (int j : e[i])
            tr1.modify(rt[i], rt[i], 1, n, j, sw[p[j]]);
    }

    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && s[j + 1] != s[i])
            j = fail[j];
        j += s[i] == s[j + 1];
        fail[i] = j;
    }
    for (int i = 1; i <= n; i++)
        pre[i] = sw[i] + pre[fail[i]];
    build(1, 1, n);

    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        int p = query(1, 1, n, l, r, r);
        // cout << p << ' ';
        if (p == N)
        {
            int ans = tr1.query(rt[r], 1, n, l, r);
            cout << ans << '\n';
        }
        else
        {
            int m = r - p + 1;
            int ans = pre[m] + tr1.query(rt[r - 1], 1, n, l, r);
            cout << ans << '\n';
        }
    }
}

bool Med;

signed main()
{
    ios;
    // fopen;
    cerr << (&Med - &Mst) / 1024 / 1024;

    int t = 1;
    srand(time(0));
    cout << fixed << setprecision(12);

    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve();
    }

    return 0;
}