#include<bits/stdc++.h>
using namespace std;
const int MOD=1e30;
long long T,n,Q,a[3005],b[3005],ans,fa[3005][3005],fb[3005][3005];
int matcha(int l,int r){
	int mid=(l+r)/2;
	if(l==r)return fa[l][r];
	fa[l][r]=max(matcha(l,mid),matcha(mid+1,r));
}
int matchb(int l,int r){
	int mid=(l+r)/2;
	if(l==r)return fb[l][r];
	fb[l][r]=max(matchb(l,mid),matchb(mid+1,r));
}
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]);
	fa[i][i]=a[i];
	}
	for(int i=1;i<=n;i++){
	scanf("%d",&b[i]);
	fb[i][i]=b[i];
	}
	matcha(1,n);
	for(int i=1;i<=(1+n)/2;i++)
	for(int j=(1+n)/2+1;j<=n;j++)
	fa[i][j]=max(fa[i][(1+n)/2],fa[(1+n)/2+1][j]);
	
	matchb(1,n);
	for(int i=1;i<=(1+n)/2;i++)
	for(int j=(1+n)/2+1;j<=n;j++)
	fb[i][j]=max(fb[i][(1+n)/2],fb[(1+n)/2+1][j]);
	
	int mid=(1+n)/2;
	fa[mid-1][mid]=max(a[mid-1],a[mid]);
	fb[mid-1][mid]=max(b[mid-1],b[mid]);
	scanf("%d",&Q);
	while(Q--){
		int l,r,ans=0;
		scanf("%d%d",&l,&r);
		for(int i=l;i<=r;i++)
		for(int j=i;j<=r;j++)
		ans+=(fa[i][j]*fb[i][j])%MOD;
		printf("%d\n",ans);
	}
	return 0;
}
/*
0 5
1 3 5 7 9
2 4 6 8 10
1
1 5
*/
