#include<bits/stdc++.h>
using namespace std;
const int N=250010;
int a[N][20],b[N][20];
int t,n,q;
void ST(){
	int k=1;
	for(int i=1;i<=log2(n);i++){
		if(i>1) k<<=1;
		for(int j=1;j+k<=n;j++){
			a[j][i]=max(a[j][i-1],a[j+k][i-1]);
			b[j][i]=max(b[j][i-1],b[j+k][i-1]);
		}
	}
}
int main(){
	freopen("match1.in","r",stdin);
	freopen("match1.out","w",stdout);
	cin>>t>>n;
	for(int i=1;i<=n;i++) cin>>a[i][0];
	for(int i=1;i<=n;i++) cin>>b[i][0];
	ST();
	cin>>q;
	while(q--){
		unsigned long long ans=0;
		int l,r;
		cin>>l>>r;
		for(int i=l;i<=r;i++){
			for(int j=i;j<=r;j++){
				int k=log2(j-i+1);
				ans+=max(a[i][k],a[j-(1<<k)+1][k])*max(b[i][k],b[j-(1<<k)+1][k]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}