#include<bits/stdc++.h>
using namespace std;
#define fo(v, a, b) for(int v = a; v <= b; v++)
#define fr(v, a, b) for(int v = a; v >= b; v--)
#define cl(a, v) memset(a, v, sizeof(a))

typedef unsigned long long ull;

const int N = 250010;

int Id, n, Q, a[N], b[N];

namespace BF {
    const int SN = 3010;
    int A[SN][SN], B[SN][SN]; ull res[SN][SN];
    void Solve() {
        fo(l,1,n) {
            A[l][l] = a[l], B[l][l] = b[l];
            fo(r,l,n) {
                A[l][r] = max(A[l][r - 1], a[r]);
                B[l][r] = max(B[l][r - 1], b[r]);
            }
        }
        fr(l,n,1) {
            fo(r,1,n) res[l][r] = res[l + 1][r];
            ull cur = 0;
            fo(r,l,n) {
                cur += A[l][r] * B[l][r];
                res[l][r] += cur;
            }
        }

        while(Q--) {
            int l, r; scanf("%d%d", &l, &r);
            printf("%llu\n", res[l][r]);
        }
    }
}

int stA[N], topA, stB[N], topB; ull ans;
inline void calc(int x, int y) {
    int l = max(stA[x - 1], stB[y - 1]), r = min(stA[x], stB[y]);
    ans += (ull)max(0, r - l + 1) * a[stA[x]] * b[stB[y]];
}

int main()
{
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);

    cin >> Id >> n;
    fo(i,1,n) scanf("%d", &a[i]);
    fo(i,1,n) scanf("%d", &b[i]);
    cin >> Q;
    
    if(max(n, Q) <= 3000)
        return BF :: Solve(), 0;

    fo(id,1,Q) {
        int L, R; scanf("%d%d", &L, &R);
        stA[topA = 0] = stB[topB = 0] = L - 1, ans = 0;
        fo(i,L,R) {
            while(topA && a[stA[topA]] <= a[i])
                topA--;
            stA[++topA] = i;
            while(topB && b[stB[topB]] <= b[i])
                topB--;
            stB[++topB] = i;
            int t = 1;
            fo(k,1,topA) {
                while(stB[t] < stA[k])
                    calc(k, t), t++;
                calc(k, t);
            }
        }
        printf("%llu\n", ans);
    }

    return 0;
}