#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const ull N=10005,mod=998244353;
ull a[N],b[N],ans[N][N];
int T,n,Q;
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for(int i=1; i<=n; i++) {
		cin>>b[i];
	}
	for(int i=1; i<=n; i++) {
		ull maxa=0,maxb=0;
		for(int j=i; j<=n; j++) {
			maxa=max(a[j],maxa);
			maxb=max(maxb,b[j]);
			ans[i][j]=maxa*maxb;
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			ans[i][j]+=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
		}
	}
	cin>>Q;
	while(Q--) {
		int l,r;
		cin>>l>>r;
		cout<<1ull*(ans[r][r]-ans[l-1][r])<<"\n";
	}
	return 0;
}