#include<bits/stdc++.h>
#define N 5005
#define int unsigned long long
using namespace std;
int T,n,a[N],b[N],mxa[N][N],mxb[N][N],ans[N][N];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%llu %llu",&T,&n);
	for(int i=1;i<=n;i++)scanf("%llu",&a[i]);
	for(int i=1;i<=n;i++)scanf("%llu",&b[i]);
	for(int i=1;i<=n;i++){
		int tmp=a[i];
		for(int j=i;j<=n;j++)tmp=max(tmp,a[j]),mxa[i][j]=tmp;
	}
	for(int i=1;i<=n;i++){
		int tmp=b[i];
		for(int j=i;j<=n;j++)tmp=max(tmp,b[j]),mxb[i][j]=tmp;
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			ans[i][j]=mxa[i][j]*mxb[i][j];
	for(int l=1;l<=n;l++)
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			ans[i][j]+=ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
		}
	int Q;scanf("%llu",&Q);
	while(Q--){
		int l,r;scanf("%llu %llu",&l,&r);
		printf("%llu\n",ans[l][r]);
	}
	return 0;
}
