#include<bits/stdc++.h>
using namespace std;
int read() {
	int res=0;
	char x;
	x=getchar();
	while(x<'0'||x>'9') {
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		res=res*10+x-'0';
		x=getchar();
	}
	return res;
}
int T,n,q;
int a[2][250005];
unsigned long long tr[2][1000005];
void bui(int op,int x,int l,int r) {
	if(l==r) {
		tr[op][x]=a[op][l];
		return ;
	}
	bui(op,x*2,l,(l+r)/2);
	bui(op,x*2+1,(l+r)/2+1,r);
	tr[op][x]=max(tr[op][x*2],tr[op][x*2+1]);
	return ;
}
unsigned long long tq[2][3003][3003];
unsigned long long ask(int op,int x,int l,int r,int ll,int rr){
	if(tq[op][ll][rr]){
		return tq[op][ll][rr];
	}
	if(l>=ll&r<=rr){
		return tr[op][x];
	}
	int mid=(l+r)/2;
	unsigned long long ans;
	if(mid<ll)ans=ask(op,x*2+1,mid+1,r,ll,rr);
	else if(mid>=rr)ans=ask(op,x*2,l,mid,ll,rr);
	else{
		ans=max(ask(op,x*2+1,mid+1,r,ll,rr),ask(op,x*2,l,mid,ll,rr));
	}
	return ans;
}
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();
	n=read();
	for(int i=1; i<=n; i++) {
		a[0][i]=read();
	}
	for(int i=1; i<=n; i++) {
		a[1][i]=read();
	}
	bui(0,1,1,n);
	bui(1,1,1,n);
	q=read();
	for(int i=1;i<=q;i++){
		int l,r;
		l=read();
		r=read();
		unsigned long long ans=0;
		for(int ll=l;ll<=r;ll++){
			for(int rr=ll;rr<=r;rr++){
				unsigned long long aa=ask(0,1,1,n,ll,rr);
				unsigned long long bb=ask(1,1,1,n,ll,rr);
				ans+=aa*bb;
				if(ll<=3000&&rr<=3000){
					tq[0][ll][rr]=aa;
					tq[1][ll][rr]=bb;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}