#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int M=3007;
ull T,n,a[M],b[M],Q,l,r,ans[M][M];
ull STa[M][M],STb[M][M],lg2[M];
stack<ll> stk;
ull querya(ll l,ll r){
	return STa[l][r];
}
ull queryb(ll l,ll r){
	return STb[l][r];
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%llu%llu",&T,&n);
	for(int i=2;i<M;i++) lg2[i]=lg2[i>>1]+1;
	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++){
		STa[i][i]=a[i];
		for(int j=i+1;j<=n;j++)
			STa[i][j]=max(STa[i][j-1],a[j]);
	}
	for(int i=1;i<=n;i++){
		STb[i][i]=b[i];
		for(int j=i+1;j<=n;j++)
			STb[i][j]=max(STb[i][j-1],b[j]);
	}
	for(int i=1;i<=n;i++)
		for(int l=1,r=i;r<=n;l++,r++)
			ans[l][r]=ans[l+1][r]+ans[l][r-1]-
			ans[l+1][r-1]+STa[l][r]*STb[l][r];
	scanf("%llu",&Q);
	while(Q--)
		scanf("%llu%llu",&l,&r),
		printf("%llu\n",ans[l][r]);
	return 0;
}