#include<bits/stdc++.h>
using namespace std;
int T,n,Q,a[310000],b[310000];
unsigned long long c[5100][5100]; int top,s[5100];
int lsa[310000],rsa[310000];
int lsb[310000],rsb[310000];
unsigned long long calc(int l,int m,int r){
    unsigned long long ans=0;
    for (int i=l;i<=r;i++){
        int x=max(l,lsb[i]+1),y=min(r,rsb[i]-1);
        int lx=max(0,m-x+1),rx=max(0,y-m+1);
        ans+=1ull*lx*rx*a[m]*b[i];
    }
    return ans;
}
int main(){
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>T>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) cin>>b[i];
    if (n<=5000){
        for (int i=1;i<=n;i++){
            int mxa=0,mxb=0;
            for (int j=i;j<=n;j++){
                mxa=max(mxa,a[j]);
                mxb=max(mxb,b[j]);
                c[i][j]=1ll*mxa*mxb;
            }
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        int l,r;
        cin>>Q;
        while (Q--){
            cin>>l>>r;
            cout<<c[r][r]-c[l-1][r]-c[r][l-1]+c[l-1][l-1]<<'\n';
        }
        return 0;
    }
    int l=1,r=n;
    top=0;
    for (int i=l;i<=r;i++){
        while (top&&a[s[top]]<a[i]) top--;
        lsa[i]=s[top]; s[++top]=i;
    }
    top=0;
    for (int i=r;i>=l;i--){
        while (top&&a[s[top]]<a[i]) top--;
        rsa[i]=s[top]; s[++top]=i;
    }
    top=0;
    for (int i=l;i<=r;i++){
        while (top&&b[s[top]]<b[i]) top--;
        lsb[i]=s[top]; s[++top]=i;
    }
    top=0;
    for (int i=r;i>=l;i--){
        while (top&&b[s[top]]<b[i]) top--;
        rsb[i]=s[top]; s[++top]=i;
    }
    cin>>Q;
    while (Q--){
        cin>>l>>r; unsigned long long ans=0;
        for (int i=l;i<=r;i++) ans+=calc(max(lsa[i]+1,l),i,min(lsb[i]-1,r));
        cout<<ans<<'\n';
    }
    return 0;
}
