#include<bits/stdc++.h>
using namespace std;
int T,n,q,a[100010],b[100010],maxna[3010][3010],maxnb[3010][3010];
unsigned long long ans[3010][3010];
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]);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
	    	maxna[i][j]=max(maxna[i][j-1],a[j]);
	    	maxnb[i][j]=max(maxnb[i][j-1],b[j]);
		}
	}
	for(int i=1;i<=n;i++)ans[i][i]=maxna[i][i]*maxnb[i][i];
	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			ans[i][j]=ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
			ans[i][j]+=maxna[i][j]*maxnb[i][j];
		}
	}
	scanf("%d",&q);
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		cout<<ans[l][r]<<endl;
	}
}