#include<bits/stdc++.h>
using namespace std;
int T,n,Q,max1,max2;
int ga[1005],gb[1005];
int a[1005],b[1005];
int ans;
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	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);
	for(int i=1;i<=Q;i++) {
		memset(ga,0,sizeof(ga));
		memset(gb,0,sizeof(gb));
		int l,r; scanf("%d%d",&l,&r);
		ans=0;
		for(int len=1;len<=r-l+1;len++) {
			int La=1,Ra=0; int Lb=1,Rb=0;
			for(int j=l;j<=len+l-1;j++) {
				while(La<=Ra&&a[j]>a[ga[Ra]]) Ra--;
				while(Lb<=Rb&&b[j]>b[gb[Rb]]) Rb--;
				ga[++Ra]=j;
				gb[++Rb]=j;
			}
			for(int j=len+l;j<=r;j++) {
				max1=a[ga[La]]; max2=b[gb[Lb]]; //cout<<max1<<" "<<max2<<" ";
				ans+=max1*max2; //cout<<ans<<"\n";
				while(La<=Ra&&j-ga[La]>=len) La++;
				while(Lb<=Rb&&j-gb[Lb]>=len) Lb++;
				while(La<=Ra&&a[j]>a[ga[Ra]]) Ra--;
				ga[++Ra]=j;
				while(Lb<=Rb&&b[j]>b[gb[Rb]]) Rb--;
				gb[++Rb]=j;
				
			}
			max1=a[ga[La]]; max2=b[gb[Lb]];
//			cout<<max1<<" "<<max2<<" ";
			ans+=max1*max2; //cout<<ans<<"\n";
		}
		printf("%d\n",ans);
	}
	return 0;
}
