#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3005;
int a[N],b[N];
ull s[N][N];int T,n,q;
void work1(){
	for(int i=1;i<=n;i++){
		int maxxa=0,maxxb=0;
		for(int j=i;j<=n;j++) {
			maxxa=max(maxxa,a[j]);
			maxxb=max(maxxb,b[j]);
			ull res=maxxa*maxxb;
		//	cout<<res<<endl;
			s[1][j]+=res;s[i+1][j]-=res;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		}
	}
	while(q--){
		int l,r;scanf("%d%d",&l,&r);
		printf("%llu\n",s[l][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]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	scanf("%d",&q);
	work1();
}
