#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull n,q,a[250005],b[250005],ta[250005],tb[250005],s[3005][3005];
ull solve(ull l,ull r){
	if(l==r)return a[l]*b[l];
	ull i,j,mid=l+r>>1,L=mid+1,LL=mid+1,R=mid,RR=mid,ans=0,sum=0,cnt=0;
	ans=solve(l,mid)+solve(mid+1,r);
	ta[mid+1]=a[mid+1];
	for(i=mid+2;i<=r;i++)ta[i]=max(ta[i-1],a[i]);
	ta[mid]=a[mid];
	for(i=mid-1;i>=l;i--)ta[i]=max(ta[i+1],a[i]);
	
	tb[mid+1]=b[mid+1];
	for(i=mid+2;i<=r;i++)tb[i]=max(tb[i-1],b[i]);
	tb[mid]=b[mid];
	for(i=mid-1;i>=l;i--)tb[i]=max(tb[i+1],b[i]);
	
	for(i=mid+1;i<=r;i++){
		while(ta[i]>=ta[L-1]&&L>l)L--,sum+=tb[L];
		if(i>mid+1)sum+=cnt*(tb[i]-tb[i-1]);
		while(tb[i]>=tb[LL-1]&&LL>L)LL--,cnt++,sum+=tb[i]-tb[LL];
		ans+=ta[i]*sum;
	}
	sum=cnt=0;
	for(i=mid;i>=l;i--){
		while(ta[i]>=ta[R+1]&&R<r)R++,sum+=tb[R];
		if(i<mid)sum+=cnt*(tb[i]-tb[i+1]);
		while(tb[i]>=tb[RR+1]&&RR<R)RR++,cnt++,sum+=tb[i]-tb[RR];
		ans+=ta[i]*sum;
	}
	return ans;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ull T,i,j;
	scanf("%llu%llu",&T,&n);
	for(i=1;i<=n;i++)scanf("%llu",&a[i]);
	for(i=1;i<=n;i++)scanf("%llu",&b[i]);
	if(n<=3000){
		for(i=1;i<=n;i++){
			ull A=a[i],B=b[i];
			for(j=i;j<=n;j++){
				A=max(A,a[j]);
				B=max(B,b[j]);
				s[i][j]=s[i][j-1]+A*B;
			}
		}
		scanf("%d",&q);
		for(i=1;i<=q;i++){
			ull ans=0,l,r;
			scanf("%llu%llu",&l,&r);
			for(j=l;j<=r;j++)ans+=s[j][r];
			printf("%llu\n",ans);
		}
	}
	else{
		scanf("%llu",&q);
		for(i=1;i<=q;i++){
			ull l,r,ans;
			scanf("%llu%llu",&l,&r);
			printf("%llu\n",solve(l,r));
		}
	}
	return 0;
}