#include<bits/stdc++.h>
using namespace std;
const int N=100001;
using ull = unsigned long long;
int a[N],b[N];
struct oper{
    int ti,tp,v;
};
void solve(int a[],int b[],int n){
    ull ans=0;
    vector<int>st1,st2;
    for(int i=1;i<=n;i++){
        while(!st1.empty()&&a[i]>a[st1.back()]){
            st1.pop_back();
        }
        st1.push_back(i);
        while(!st2.empty()&&b[i]>b[st2.back()]){
            st2.pop_back();
        }
        st2.push_back(i);
        vector<oper>ops;
        for(auto v:st1){
            ops.push_back({v,1,a[v]});
        }
        for(auto v:st2){
            ops.push_back({v,2,b[v]});
        }
        sort(ops.begin(),ops.end(),[&](oper a,oper b){return a.ti<b.ti;});
        int tim=1,A=0,B=0;
        for(int i=ops.size()-1;i>=0;){
            tim=ops[i].ti;
            while(i>=0&&ops[i].ti==tim){
                if(ops[i].tp==1)A=ops[i].v;
                else B=ops[i].v;
                --i;
            }
            if(i>=0)ans=ans+1ull*A*B*(tim-ops[i].ti);
            else ans=ans+1ull*A*B*(tim);
        }
    }
    printf("%llu\n",ans);
    //cout<<ans<<'\n';
}
int main(){
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    int T,n,Q; 
    scanf("%d%d",&T,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    scanf("%d",&Q);
    while(Q--){
        int l,r;
        scanf("%d%d",&l,&r);
        solve(a+l-1,b+l-1,r-l+1);
        
    }
}
