#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
struct tag {
    ull da, db, dt;
    ull sa, sb, sab;
} t[1000010], Itag{0, 0, 0, 0, 0, 0};
struct inf {
    ull cnt, sa, sb, sab, ans;
} f[1000010];
inf operator + (const inf &a, const inf &b) {
    return {a.cnt + b.cnt, a.sa + b.sa, a.sb + b.sb, a.sab + b.sab, a.ans + b.ans};
}
inf& operator += (inf &a, const tag &b) {
    return a = {a.cnt, a.sa + b.da * a.cnt, a.sb + b.db * a.cnt, a.sab + b.da * b.db * a.cnt + b.da * a.sb + b.db * a.sa,
                a.ans + a.sab * b.dt + a.sa * b.sb + a.sb * b.sa + a.cnt * b.sab};
}
tag& operator += (tag &a, const tag &b) {
    tag ans = {
        a.da + b.da, a.db + b.db, a.dt + b.dt,
        a.sa + b.sa + a.da * b.dt,
        a.sb + b.sb + a.db * b.dt,
        a.sab + b.sab + a.da * b.sb + a.db * b.sa + a.da * a.db * b.dt
    };
    return a = ans;
}
void down(int x) {
    t[x << 1] += t[x];
    f[x << 1] += t[x];
    t[x << 1 | 1] += t[x];
    f[x << 1 | 1] += t[x];
    t[x] = Itag;
}
void up(int x) {
    f[x] = f[x << 1] + f[x << 1 | 1];
}
void modify(int x, int l, int r, int L, int R, const tag &v) {
    if (l > R || L > r) return;
    if (L <= l && r <= R) {
        t[x] += v;
        f[x] += v;
        return;
    }
    int mid = l + r >> 1;
    down(x);
    modify(x << 1, l, mid, L, R, v);
    modify(x << 1 | 1, mid + 1, r, L, R, v);
    up(x);
}
ull query(int x, int l, int r, int L, int R) {
    if (l > R || L > r) return 0;
    if (L <= l && r <= R) return f[x].ans;
    int mid = l + r >> 1;
    down(x);
    return query(x << 1, l, mid, L, R) + query(x << 1 | 1, mid + 1, r, L, R);
}
void build(int x, int l, int r) {
    if (l == r) {
        f[x].cnt = 1;
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    up(x);
}
int n, m;
ull ans[250010];
int a[250010], b[250010];
vector < pair <int, int> > q[250010];
int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    scanf("%*d%d", &n);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) scanf("%d", b + i);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        q[r].push_back({l, i});
    }
    a[0] = b[0] = n + 1;
    vector <int> staa{0}, stab{0};
    for (int i = 1; i <= n; i++) {
        modify(1, 1, n, i, i, {(ull)a[i], (ull)b[i], 0, 0, 0, 0});
        while (a[staa.back()] < a[i]) {
            int tmp = staa.back();
            staa.pop_back();
            modify(1, 1, n, staa.back() + 1, tmp, {(ull)(a[i] - a[tmp]), 0, 0, 0, 0, 0});
        }
        while (b[stab.back()] < b[i]) {
            int tmp = stab.back();
            stab.pop_back();
            modify(1, 1, n, stab.back() + 1, tmp, {0, (ull)(b[i] - b[tmp]), 0, 0, 0, 0});
        }
        staa.push_back(i);
        stab.push_back(i);
        modify(1, 1, n, 1, i, {0, 0, 1, 0, 0, 0});
        for (auto v : q[i])
            ans[v.second] = query(1, 1, n, v.first, i);
    }
    for (int i = 1; i <= m; i++) printf("%llu\n", ans[i]);
}