#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=3e5+5;
int _,n,Q;
struct segtree{
    #define mid ((l+r)/2)
    #define seg int p,int l,int r
    #define lid p<<1,l,mid
    #define rid p<<1|1,mid+1,r
    void build(seg){
        sa[p]=sb[p]=ans[p]=la[p]=lb[p]=0;
        if(l==r)return;
        build(lid),build(rid);
    }
    void pp(int p){
        sa[p]=sa[p<<1]+sa[p<<1|1];
        sb[p]=sb[p<<1]+sb[p<<1|1];
        ans[p]=ans[p<<1]+ans[p<<1|1];
    }
    void work1(seg,int z){
        la[p]=z;
        sa[p]=(ull)(r-l+1)*z;
        ans[p]=z*sb[p];
    }
    void work2(seg,int z){
        lb[p]=z;
        sb[p]=(ull)(r-l+1)*z;
        ans[p]=z*sa[p];
    }
    void pd(seg){
        if(la[p])work1(lid,la[p]),work1(rid,la[p]),la[p]=0;
        if(lb[p])work2(lid,lb[p]),work2(rid,lb[p]),lb[p]=0;
    }
    void add1(seg,int L,int R,int z){
        if(l>=L&&r<=R){
            work1(p,l,r,z);
            return;
        }
        if(la[p]||lb[p])pd(p,l,r);
        if(L<=mid)add1(lid,L,R,z);
        if(R>mid)add1(rid,L,R,z);
        pp(p);
    }
    void add2(seg,int L,int R,int z){
        if(l>=L&&r<=R){
            work2(p,l,r,z);
            return;
        }
        if(la[p]||lb[p])pd(p,l,r);
        if(L<=mid)add2(lid,L,R,z);
        if(R>mid)add2(rid,L,R,z);
        pp(p);
    }
    ull sa[N<<2],sb[N<<2],ans[N<<2];
    int la[N<<2],lb[N<<2];
}tr;
int a[N],b[N],st1[N],st2[N];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>_>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    cin>>Q;
    for(int l,r;Q--;){
        cin>>l>>r;ull ans=0;
        int top1=0,top2=0;
        tr.build(1,1,n);
        for(int i=l;i<=r;i++){
            while(top1&&a[st1[top1]]<a[i])top1--;
            if(!top1)tr.add1(1,1,n,l,i,a[i]);
            else tr.add1(1,1,n,st1[top1]+1,i,a[i]);
            st1[++top1]=i;
            while(top2&&b[st2[top2]]<b[i])top2--;
            if(!top2)tr.add2(1,1,n,l,i,b[i]);
            else tr.add2(1,1,n,st2[top2]+1,i,b[i]);
            st2[++top2]=i;
            ans+=tr.ans[1];
        }
        cout<<ans<<'\n';
    }
}