#include <bits/stdc++.h>
#define sz(a) int((a).size())
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define ll long long
#define vi vector<int>
#define ull unsigned long long

using namespace std;
const int N = 2.5e5 + 10;
int T, n, Q;
int la[N], ra[N], lb[N], rb[N], stk[N], tp = 0;
ull a[N], b[N], ans[N];
vector<tuple<int, int, ull>> ga[N], gb[N];
vector<tuple<int, int, int, ull>> qry[N];
void init(ull a[], int l[], int r[]) {
    tp = 0;
    a[0] = a[n + 1] = n + 1;
    stk[++tp] = 0;
    FOR(i, 1, n) {
        while(tp && a[stk[tp]] < a[i]) r[stk[tp]] = i, tp--;
        l[i] = stk[tp], stk[++tp] = i;
    }
    while(tp) r[stk[tp]] = n + 1, tp--;
}
#define mid ((l + r) >> 1)
#define ls (p + 1)
#define rs (p + ((mid - l + 1) << 1))
ull sa[N << 1], sb[N << 1], sab[N << 1], sh[N << 1];
ull ta[N << 1], tb[N << 1], th1[N << 1], th2[N << 1], th3[N << 1], th4[N << 1];
void up(int p, int l, int r) {
    sa[p] = sa[ls] + sa[rs];
    sb[p] = sb[ls] + sb[rs];
    sab[p] = sab[ls] + sab[rs];
    sh[p] = sh[ls] + sh[rs];
}
void dw(int p, int l, int r, ull a, ull b, ull h1, ull h2, ull h3, ull h4) {
    sh[p] += sab[p] * h1 + sa[p] * h2 + sb[p] * h3 + h4 * (r - l + 1);
    th1[p] += h1;
    th2[p] += tb[p] * h1;
    th3[p] += ta[p] * h1;
    th4[p] += h1 * ta[p] * tb[p];
    th2[p] += h2;
    th4[p] += h2 * ta[p];
    th3[p] += h3;
    th4[p] += h3 * tb[p];
    th4[p] += h4;
    ta[p] += a, tb[p] += b;
    sab[p] += sb[p] * a;
    sa[p] += (r - l + 1) * a;
    sab[p] += sa[p] * b;
    sb[p] += (r - l + 1) * b;
}
void pd(int p, int l, int r) {
    dw(ls, l, mid, ta[p], tb[p], th1[p], th2[p], th3[p], th4[p]);
    dw(rs, mid + 1, r, ta[p], tb[p], th1[p], th2[p], th3[p], th4[p]);
    ta[p] = tb[p] = th1[p] = th2[p] = th3[p] = th4[p] = 0;
}
void modify(int p, int l, int r, int L, int R, ull a, ull b, ull h1) {
    if(L <= l && r <= R) {
        dw(p, l, r, a, b, h1, 0, 0, 0);
        return;
    }
    pd(p, l, r);
    if(L <= mid) modify(ls, l, mid, L, R, a, b, h1);
    if(R > mid) modify(rs, mid + 1, r, L, R, a, b, h1);
    up(p, l, r);
}
ull query(int p, int l, int r, int L, int R) {
    if(L <= l && r <= R) return sh[p];
    pd(p, l, r);
    ull res = 0;
    if(L <= mid) res += query(ls, l, mid, L, R);
    if(R > mid) res += query(rs, mid + 1, r, L, R);
    return res;
}
void dfs(int p, int l, int r) {
    if(l == r) return;
    pd(p, l, r);
    dfs(ls, l, mid), dfs(rs, mid + 1, r);
    up(p, l, r);
}
int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
    init(a, la, ra), init(b, lb, rb);
    FOR(i, 1, n) {
        la[i]++, ra[i]--, lb[i]++, rb[i]--;
        ga[la[i]].emplace_back(i, ra[i], a[i]);
        ga[i + 1].emplace_back(i, ra[i], -a[i]);
        gb[lb[i]].emplace_back(i, rb[i], b[i]);
        gb[i + 1].emplace_back(i, rb[i], -b[i]);
    }
    cin >> Q;
    FOR(i, 1, Q) {
        int l, r;
        cin >> l >> r;
        qry[r].emplace_back(l, r, i, 1);
        qry[l - 1].emplace_back(l, r, i, -1);
    }
    FOR(i, 0, n) {
        for(auto [l, r, v] : ga[i]) {
            modify(1, 1, n, l, r, v, 0, 0);
        }
        for(auto [l, r, v] : gb[i]) {
            modify(1, 1, n, l, r, 0, v, 0);
        }
        modify(1, 1, n, 1, n, 0, 0, 1);
        for(auto [l, r, id, v] : qry[i]) {
            ans[id] += query(1, 1, n, l, r) * v;
        }
    }
    FOR(i, 1, Q) cout << ans[i] << "\n";
}
