// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
typedef unsigned long long mint;
int T, n, q, a[250005], b[250005], ql[250005], qr[250005];
mint sum[250005], tot;
void add(int pos, mint val)
{
    tot += val;
    while (pos <= n)
    {
        sum[pos] += val;
        pos += pos & -pos;
    }
}
mint query(int pos)
{
    mint res = 0;
    while (pos)
    {
        res += sum[pos];
        pos -= pos & -pos;
    }
    return res;
}
struct node
{
    int a, b;
    mint cnt;
};
mint work(std::vector<node> &A,
          std::vector<node> &B)
{
    mint res = 0;
    // for (auto i : A)
    //     for (auto j : B)
    //         res += i.cnt * j.cnt * std::max(i.a, j.a) * std::max(i.b, j.b);
    // return res;
    // for (auto i : A)
    //     std::cout << i.a << ' ' << i.b << ' ' << i.cnt << std::endl;
    // for (auto i : B)
    //     std::cout << i.a << ' ' << i.b << ' ' << i.cnt << std::endl;
    // std::sort(A.begin(), A.end(), [&](const node &A, const node &B)
    //           { return A.a < B.a; });
    // std::sort(B.begin(), B.end(), [&](const node &A, const node &B)
    //           { return A.a < B.a; });
    for (int i = 0; i != 2; ++i)
    {
        std::size_t a = 0;
        for (std::size_t b = 0; b != B.size(); ++b)
        {
            while (a != A.size() && A[a].a < B[b].a)
                add(A[a].b, A[a].cnt), ++a;
            res += B[b].cnt * B[b].a * B[b].b * query(B[b].b);
        }
        while (a)
        {
            --a;
            add(A[a].b, -A[a].cnt);
        }
        for (std::size_t b = 0; b != B.size(); ++b)
        {
            while (a != A.size() && A[a].a < B[b].a)
                add(A[a].b, A[a].cnt * A[a].b), ++a;
            res += B[b].cnt * B[b].a * (tot - query(B[b].b));
        }
        while (a)
        {
            --a;
            add(A[a].b, -A[a].cnt * A[a].b);
        }
        A.swap(B);
    }
    return res;
}
mint solve(int l, int r)
{
    if (l == r)
        return 1llu * a[l] * b[l];
    int mid = (l + r) >> 1;
    std::vector<node> L, R;
    int ma = 0, mb = 0;
    for (int i = mid; i >= l; --i)
    {
        ma = std::max(ma, a[i]);
        mb = std::max(mb, b[i]);
        if (!L.empty() && L.back().a == ma && L.back().b == mb)
            ++L.back().cnt;
        else
            L.push_back({ma, mb, 1});
    }
    ma = mb = 0;
    for (int i = mid + 1; i <= r; ++i)
    {
        ma = std::max(ma, a[i]);
        mb = std::max(mb, b[i]);
        if (!R.empty() && R.back().a == ma && R.back().b == mb)
            ++R.back().cnt;
        else
            R.push_back({ma, mb, 1});
    }
    return work(L, R) + solve(l, mid) + solve(mid + 1, r);
}
signed main()
{
    freopen("match.in", "r", stdin) && freopen("match.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin >> T >> n;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= n; ++i)
        std::cin >> b[i];
    std::cin >> q;
    for (int i = 1; i <= q; ++i)
        std::cin >> ql[i] >> qr[i];
    if (n <= 3000)
    {
        mint ans[3005][3005];
        std::memset(ans, 0, sizeof(ans));
        for (int i = 1; i <= n; ++i)
        {
            int A = 0, B = 0;
            for (int j = i; j <= n; ++j)
            {
                A = std::max(A, a[j]);
                B = std::max(B, b[j]);
                ans[i][j] = 1llu * A * B;
            }
        }
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; ++j)
                ans[i][j] += ans[i][j - 1];
        for (int i = n; i; --i)
            for (int j = i; j <= n; ++j)
                ans[i][j] += ans[i + 1][j];
        for (int i = 1; i <= q; ++i)
            std::cout << ans[ql[i]][qr[i]] << '\n';
    }
    else if (q <= 5)
    {
        for (int i = 1; i <= q; ++i)
            std::cout << solve(ql[i], qr[i]) << '\n';
    }
    return 0;
}