UOJ

/*
    \  | ^  ^  \
   -- | #    # \
   \_|         \
*/
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long

const int N = 2e6 + 10, M = 2e6 + 10;

int id[N];
int st[21][N * 2];
int L[N], cnt, vis[N];
int topo[N], topocnt;
int Lg[N * 2];
int top[N], ed[N];
int n, m, q;
int dfncnt;
int f[N], g[N];
int fa[N][21];
ll sum[N];
int siz[N];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

void write(ll x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

struct SAM {
    int dep[N], len[N];
    int tot, ver[N], pos[N], link[N];
    int ch[N][26];
    int dfn[N];
    std::vector<int> path[N];

    SAM() {
        tot = 1;
    }

    int append(int las, int c) {
        int p = las, cur = ++tot;
        len[cur] = len[p] + 1;
        while (p && !ch[p][c]) {
            ch[p][c] = cur;
            p = link[p];
        }
        if (!p) link[cur] = 1;
        else {
            int q = ch[p][c];
            if (len[q] == len[p] + 1) link[cur] = q;
            else {
                int clone = ++tot;
                for (int i = 0; i < 26; ++i) {
                    ch[clone][i] = ch[q][i];
                }
                link[clone] = link[q], len[clone] = len[p] + 1;
                while (p && ch[p][c] == q) {
                    ch[p][c] = clone;
                    p = link[p];
                }
                link[q] = clone, link[cur] = clone;
            }
        }
        return cur;
    }

    void get_pos(int u) {
        for (auto v : path[u]) {
            get_pos(v);
            pos[u] = pos[v];
        }
    }

    void init(char* s) {
        int len = strlen(s + 1);
        ver[0] = tot = 1;
        for (int i = 1; i <= n; ++i) {
            ver[i] = append(ver[i - 1], s[i]);
        }
        for (int i = 2; i <= tot; ++i) {
            path[link[i]].push_back(i);
        }
        for (int i = 1; i <= n; ++i) {
            pos[ver[i]] = i;
        }
        get_pos(1);
    }

    void dfs_lcp(int u) {
        L[u] = ++cnt;
        dfn[u] = ++tot;
        st[0][cnt] = len[u];
        for (auto v : path[u]) {
            dfs_lcp(v);
            st[0][++cnt] = len[u];
        }
    }

    void init_lcp() {
        tot = 0;
        dfs_lcp(1);
        for (int k = 1; k <= 20; ++k) {
            for (int i = 1; i <= cnt - (1 << k) + 1; ++i) {
                st[k][i] = std::min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
            }
        }
    }

    int lcp(int x, int y) {
        x = L[ver[x]], y = L[ver[y]];
        if (x > y) std::swap(x, y);
        int lg = Lg[y - x + 1];
        return std::min(st[lg][x], st[lg][y - (1 << lg) + 1]);
    }

    void dfstopo(int u) {
        vis[u] = 1;
        for (int i = 0; i < 26; ++i) {
            int v = ch[u][i];
            if (v && !vis[v]) dfstopo(v);
        }
        topo[++topocnt] = u;
    }

    void dfsdfn(int u, int _top) {
        dfn[u] = ++dfncnt, id[dfn[u]] = u;
        top[u] = _top;
        for (int i = 0; i < 26; ++i) {
            int v = ch[u][i];
            if (v && !dfn[v] && f[v] < f[u] * 2 && g[u] < g[v] * 2) dfsdfn(v, _top);
        }
        ed[u] = id[dfncnt];
    }

    void dagdiv() {
        dfstopo(1);
        memset(vis, 0, sizeof(vis));
        f[1] = 1;
        for (int i = 1; i <= topocnt; ++i) g[i] = 1;
        for (int i = topocnt; i; --i) {
            int u = topo[i];
            for (int j = 0; j < 26; ++j) {
                if (ch[u][j]) f[ch[u][j]] += f[u];
            }
        }
        for (int i = 1; i <= topocnt; ++i) {
            int u = topo[i];
            for (int j = 0; j < 26; ++j) {
                if (ch[u][j]) g[u] += g[ch[u][j]];
            }
        }
        for (int i = topocnt; i; --i) {
            int u = topo[i];
            if (!dfn[u]) dfsdfn(u, u);
        }
    }

    void getfa() {
        for (int i = 2; i <= tot; ++i) {
            fa[i][0] = link[i];
        }
        for (int k = 1; k <= 20; ++k) {
            for (int i = 1; i <= tot; ++i) {
                fa[i][k] = fa[fa[i][k - 1]][k - 1];
            }
        }
    }

    int findpos(int l, int r) {
        int u = ver[r];
        int Len = r - l + 1;
        for (int i = 20; ~i; --i) {
            if (fa[u][i] && len[fa[u][i]] >= Len) {
                u = fa[u][i];
            }
        }
        return u;
    }


}ls, rs;

ll ans[M];
int tl[M], tr[M], ql[M], qr[M];
char s[N];

struct Que {
    int l, r, id;
};

std::vector<int> cha[N * 2];
std::vector<Que> que[N * 2];

namespace bit {
    int n;
    int val[N * 2];

    void change(int x, int v) {
        for (int i = x; i <= n; i += i & -i) {
            val[i] += v;
        }
    }

    ll query(int x) {
        ll res = 0;
        for (int i = x; i; i -= i & -i) {
            res += val[i];
        }
        return res;
    }

    ll query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

void dfs(int u) {
    for (auto v : ls.path[u]) {
        sum[ls.dfn[v]] += sum[ls.dfn[u]] + siz[u];
        dfs(v);
    }
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio();
    std::cin.tie(0), std::cout.tie(0);
    n = read(), m = read(), q = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) {
        s[i] -= 'a';
    }
    ls.init(s), ls.getfa();
    ls.dagdiv();
    std::reverse(s + 1, s + n + 1);
    rs.init(s), rs.init_lcp();
    std::reverse(s + 1, s + n + 1);
    for (int i = 1; i <= m; ++i) {
        tl[i] = read(), tr[i] = read();
    }
    for (int i = 1; i <= q; ++i) {
        ql[i] = read(), qr[i] = read();
    }
    bit::n = ls.tot * 2;
    Lg[1] = 0;
    for (int i = 2; i <= cnt; ++i) {
    	Lg[i] = Lg[i / 2] + 1;
    }
    for (int i = 1; i <= m; ++i) {
        int u = ls.findpos(tl[i], tr[i]);
        ++siz[u];
        cha[tr[i] - tl[i] + 1 - ls.dfn[u] + ls.tot].push_back(ls.dfn[u]);
    }
    dfs(1);
    for (int i = 1; i <= ls.tot; ++i) sum[i] += sum[i - 1];
    for (int i = 1; i <= q; ++i) {
        int nl = 1, len = qr[i] - ql[i] + 1, u = ls.ch[1][s[ql[i]]];
        while (nl <= len) {
            int cl = ls.pos[ed[u]] - (ls.dfn[ed[u]] - ls.dfn[u]);
            int z = std::min(rs.lcp(n - (ql[i] + nl - 1) + 1, n - cl + 1) - 1, std::min(len - nl, ls.dfn[ed[u]] - ls.dfn[u]));
            ans[i] += sum[ls.dfn[u] + z] - sum[ls.dfn[u] - 1];
            que[nl - ls.dfn[u] + ls.tot].push_back((Que){ls.dfn[u], ls.dfn[u] + z, i});
            nl += z;
            u = id[ls.dfn[u] + z];
            if (nl >= len) break;
            nl++;
            u = ls.ch[u][s[nl + ql[i] - 1]];
        }
    }
    for (int i = 0; i <= 2 * ls.tot; ++i) {
        for (auto it : cha[i]) bit::change(it, 1);
        for (auto it : que[i]) ans[it.id] += bit::query(it.l, it.r);
    }

    for (int i = 1; i <= q; ++i) {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}