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

namespace IO {
inline int read() {
    int x = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
    return f ? -x : x;
}
template<typename T>
inline void write(T x) {
    static int stk[65], top;
    top = 0;
    if (x < 0) putchar('-'), x = -x;
    do {
        stk[++top] = x % 10;
        x /= 10;
    } while (x);
    while (top) {
        putchar(stk[top] + '0');
        top--;
    }
}
template<typename T>
inline void write(T x, char ch) {
    write(x), putchar(ch);
}
}

using pii = pair<int, int>;
using u64 = unsigned long long;

#define int u64

const int N = 250005;

u64 ans[N];
vector<pii> ask[N];
int a[N], b[N];
int stka[N], topa;
int stkb[N], topb;
int n, m, q;

struct SMT {
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    int Len[N << 2];
    u64 dta[N << 2], dtb[N << 2];
    u64 suma[N << 2], sumb[N << 2], sumab[N << 2];
    u64 val[N << 2], v0[N << 2], va[N << 2], vb[N << 2], vab[N << 2];
    void pushup(int u) {
        suma[u] = suma[ls] + suma[rs];
        sumb[u] = sumb[ls] + sumb[rs];
        sumab[u] = sumab[ls] + sumab[rs];
        val[u] = val[ls] + val[rs];
    }
    void pushval(int u, u64 V0, u64 VA, u64 VB, u64 VAB) {
        val[u] += V0 * Len[u] + VA * suma[u] + VB * sumb[u] + VAB * sumab[u];
        v0[u] += V0 * dta[u] * dtb[u], va[u] += VA * dtb[u], vb[u] += VB * dta[u], vab[u] += VAB;
    }
    void pushdt(int u, u64 DTA, u64 DTB) {
        sumab[u] += DTA * sumb[u] + DTB * suma[u] + DTA * DTB * Len[u];
        suma[u] += DTA * Len[u];
        sumb[u] += DTB * Len[u];
        dta[u] += DTA, dtb[u] += DTB;
    }
    void pushdown(int u) {
        // va, vb, vab
        pushval(ls, v0[u], va[u], vb[u], vab[u]);
        pushval(rs, v0[u], va[u], vb[u], vab[u]);
        v0[u] = va[u] = vb[u] = vab[u] = 0;
        // dta, dtb
        pushdt(ls, dta[u], dtb[u]);
        pushdt(rs, dta[u], dtb[u]);
        dta[u] = dtb[u] = 0;
    }
    void build(int u, int l, int r) {
        Len[u] = r - l + 1;
        if (l == r) return;
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
    }
    void adda(int u, int l, int r, int ql, int qr, int dlt) {
        if (ql <= l && r <= qr) {
            sumab[u] += sumb[u] * dlt;
            suma[u] += dlt * Len[u];
            dta[u] += dlt;
            return;
        }
        pushdown(u);
        int mid = l + r >> 1;
        if (ql <= mid) adda(ls, l, mid, ql, qr, dlt);
        if (qr > mid) adda(rs, mid + 1, r, ql, qr, dlt);
        pushup(u);
    }
    void addb(int u, int l, int r, int ql, int qr, int dlt) {
        if (ql <= l && r <= qr) {
            sumab[u] += suma[u] * dlt;
            sumb[u] += dlt * Len[u];
            dtb[u] += dlt;
            return;
        }
        pushdown(u);
        int mid = l + r >> 1;
        if (ql <= mid) addb(ls, l, mid, ql, qr, dlt);
        if (qr > mid) addb(rs, mid + 1, r, ql, qr, dlt);
        pushup(u);
    }
    void stop(int u, int l, int r, int ql, int qr, int dlt) {
        if (ql <= l && r <= qr) {
            val[u] += dlt * sumab[u];
            vab[u] += dlt;
            va[u] += dtb[u] * dlt;
            vb[u] += dta[u] * dlt;
            v0[u] += dta[u] * dtb[u] * dlt;
            return;
        }
        pushdown(u);
        int mid = l + r >> 1;
        if (ql <= mid) stop(ls, l, mid, ql, qr, dlt);
        if (qr > mid) stop(rs, mid + 1, r, ql, qr, dlt);
        pushup(u);
    }
    u64 qval(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return val[u];
        pushdown(u);
        int mid = l + r >> 1;
        u64 ret = 0;
        if (ql <= mid) ret += qval(ls, l, mid, ql, qr);
        if (qr > mid) ret += qval(rs, mid + 1, r, ql, qr);
        return ret;
    }
    u64 qab(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return sumab[u];
        pushdown(u);
        int mid = l + r >> 1;
        u64 ret = 0;
        if (ql <= mid) ret += qab(ls, l, mid, ql, qr);
        if (qr > mid) ret += qab(rs, mid + 1, r, ql, qr);
        return ret;
    }
    void dfs(int u, int l, int r) {
        if (l == r) return;
        pushdown(u);
        int mid = l + r >> 1;
        dfs(ls, l, mid), dfs(rs, mid + 1, r);
    }
} smt;

signed main() {
    freopen("match.in", "r", stdin);
    // freopen("match.out", "w", stdout);
    IO::read(), n = IO::read();
    for (int i = 1; i <= n; i++) a[i] = IO::read();
    for (int i = 1; i <= n; i++) b[i] = IO::read();
    a[0] = b[0] = n + 1;
    q = IO::read();
    for (int i = 1; i <= q; i++) {
        int l = IO::read(), r = IO::read();
        ask[r].push_back({l, i});
    }
    smt.build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        while (topb && b[stkb[topb]] < b[i]) {
            smt.stop(1, 1, n, stkb[topb - 1] + 1, stkb[topb], i);
            smt.addb(1, 1, n, stkb[topb - 1] + 1, stkb[topb], b[i] - b[stkb[topb]]);
            smt.stop(1, 1, n, stkb[topb - 1] + 1, stkb[topb], -i);
            topb--;
        }
        stkb[++topb] = i;
        smt.addb(1, 1, n, i, i, b[i]);
        while (topa && a[stka[topa]] < a[i]) {
            smt.stop(1, 1, n, stka[topa - 1] + 1, stka[topa], i);
            smt.adda(1, 1, n, stka[topa - 1] + 1, stka[topa], a[i] - a[stka[topa]]);
            smt.stop(1, 1, n, stka[topa - 1] + 1, stka[topa], -i);
            topa--;
        }
        stka[++topa] = i;
        smt.adda(1, 1, n, i, i, a[i]);
        smt.stop(1, 1, n, i, i, -i);
        for (int j = 0; j < ask[i].size(); j++) {
            int l = ask[i][j].first, id = ask[i][j].second;
            ans[id] = smt.qval(1, 1, n, l, i) + (i + 1) * smt.qab(1, 1, n, l, i);
            // for(int t=l;t<=i;t++)
            //     ans[id]+=smt.qval(1,1,n,t,t)+(i+1)*smt.qab(1,1,n,t,t);
        }
        smt.dfs(1, 1, n);
        // if(i<=10);
        // else continue;
        for(int j=1;j<=i;j++)
            printf("%llu ",smt.qval(1,1,n,j,j)+(i+1)*smt.qab(1,1,n,j,j));
            // printf("%llu ",smt.qab(1,1,n,j,j));
        puts("");
    }
    for (int i = 1; i <= q; i++) IO::write(ans[i], '\n');
    return 0;
}

/*
0 2
2 1
1 2
1
1 2
*/