#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long lli;

lli n,Q;
vector<lli> a,b;
//
lli cha1(lli p,lli l,lli r)
{
    lli i,j,s=0;
    vector<lli> dpa(r+10);
    vector<lli> dpb(r+10);
    for(i=p;i<=r;i++)
    {
        dpa[i]=dpa[i-1]>a[i]?dpa[i-1]:a[i];
        dpb[i]=dpb[i-1]>b[i]?dpb[i-1]:b[i];
        s=s+dpa[i]*dpb[i];
    }
    return s;
}
//
lli cha(lli l,lli r)
{
    lli i,j,s=0,x,xa=0,xb=0,xc,ca,cb,ii,jj;
    vector<lli> dpa(r+10);
    vector<lli> dpb(r+10);
    for(i=l;i<=r;i++)
    {
        if(dpa[i-1]>a[i]){dpa[i]=dpa[i-1];xa++;}
        else{dpa[i]=a[i];xa=0;}
        if(dpb[i-1]>b[i]){dpb[i]=dpb[i-1];xb++;}
        else{dpb[i]=b[i];xb=0;}
        x=dpa[i]*dpb[i];
        s=s+x;
        if(xa>xb){xc=xa;}
        else{xc=xb;}
        s=s+x*(i-l);
    }
    return s;
}
//
int main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    lli T,i,k,p,s,l,r;
    cin>>T>>n;
    a.resize(n+10);
    b.resize(n+10);
    for(i=1;i<=n;i++){cin>>a[i];}
    for(i=1;i<=n;i++){cin>>b[i];}
    cin>>Q;
    for(k=0;k<Q;k++)
    {
        cin>>l>>r;
        if(n<=30)
        {
            s=0;
            for(p=l;p<=r;p++)
            {
                s=cha1(p,l,r)+s;
            }
        }
        else{s=cha(l,r);}
        cout<<s<<endl;
    }
    return 0;
}

