#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=3e3+5;
int t,n,q,a[N],b[N],mx1[N][N],mx2[N][N],l,r;
ull s[N][N];
ull query(int x1,int x2,int y1,int y2){
	return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
signed 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<=n;i++)
		for(int j=i;j<=n;j++)
			mx1[i][j]=max(mx1[i][j-1],a[j]),mx2[i][j]=max(mx2[i][j-1],b[j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1ull*mx1[i][j]*mx2[i][j];
	while(q--){
		scanf("%d%d",&l,&r);
		printf("%llu\n",query(l,r,l,r));
	}
	return 0;
}