#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>

typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,a,b) for(int i=a,_ds##i=b;i<=_ds##i;++i)
#define per(i,a,b) for(int i=a,_ds##i=b;i>=_ds##i;--i)
template<typename T> T rd(){T r;char c,n=0;while(!isdigit(c=getchar()))n=c=='-';r=c-'0';while(isdigit(c=getchar()))r=r*10+c-'0';return n?-r:r;}
#define rdi rd<int>
#define rdl rd<LL>

const int N = 250005;
int T, n;
ULL a[N], b[N];
int paaa[N], pbbb[N];
int qa[20][N], qb[20][N];
int pw[21];

int gA(int l, int r) {
    int det = r-l+1;
    int ret = 0;
    for (int i=0; det; det>>=1, ++i) if (det & 1) {
        ret = std::max(ret, qa[i][l]);
        l = l+pw[i];
    }
    return paaa[ret];
}
int gB(int l, int r) {
    int det = r-l+1;
    int ret = 0;
    for (int i=0; det; det>>=1, ++i) if (det & 1) {
        ret = std::max(ret, qb[i][l]);
        l = l+pw[i];
    }
    return pbbb[ret];
}

ULL cA(int l, int r, int d) {
    if (l>r) return 0;
    if (r<d || l>d) return 0;
    if (l==r) return a[l];
    int x = gA(l, r);
    ULL ret = a[x];
    if (d==x) ret = ret * (x-l+1) * (r-x+1);
    else if (d<x) ret = ret * (d-l+1) * (r-x+1);
    else if (d>x) ret = ret * (x-l+1) * (r-d+1);
    return ret + cA(l, x-1, d) + cA(x+1, r, d);
}
ULL cB(int l, int r, int d) {
    if (l>r) return 0;
    if (r<d || l>d) return 0;
    if (l==r) return b[l];
    int x = gB(l, r);
    ULL ret = b[x];
    if (d==x) ret = ret * (x-l+1) * (r-x+1);
    else if (d<x) ret = ret * (d-l+1) * (r-x+1);
    else if (d>x) ret = ret * (x-l+1) * (r-d+1);
    return ret + cB(l, x-1, d) + cB(x+1, r, d);
}

ULL Solve(int l, int r) {
    if (l == r) return a[l] * b[l];
    if (l > r) return 0;
    int x = gA(l, r);
    int y = gB(l, r);
    ULL ret = a[x] * b[y];
    int X = std::min(x, y);
    int Y = std::max(x, y);
    ret = ret * (X - l + 1) * (r - Y + 1);
    ret += Solve(l, X - 1) + Solve(Y + 1, r);
    if (x != y) {
        if (x < y) {
            ret += a[x] * cB(l, y-1, x);
            ret += b[y] * cA(x+1, r, y);
        } else {
            ret += a[x] * cB(y+1, r, x);
            ret += b[y] * cA(l, x-1, y);
        }
    }
    return ret;
}

int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    T = rdi(), n = rdi();
    pw[0]=1;
    rep(i, 1, 20) pw[i] = pw[i-1] * 2;
    rep(i, 1, n) {
        int x = rdi();
        a[i] = qa[0][i] = x;
        paaa[x] = i;
    }
    rep(i, 1, n) {
        int x = rdi();
        b[i] = qb[0][i] = x;
        pbbb[x] = i;
    }
    rep(k, 1, 19)
        rep(i, 1, n) {
            int j = std::min(n, i+pw[k-1]);
            qa[k][i] = std::max(qa[k-1][i], qa[k-1][j]);
            qb[k][i] = std::max(qb[k-1][i], qb[k-1][j]);
        }
    int Q = rdi();
    while (Q--) {
        int l, r;
        l = rdi(), r = rdi();
        printf("%llu\n", Solve(l, r));
    }
    return 0;
}
