#include<bits/stdc++.h>
using namespace std;
const int N=2500005;
typedef unsigned long long ll;
int n,Q;
ll p[N],q[N],sum;
int l,r;

void solve(){
	sum=0;
	for(int pl=l;pl<=r;pl++){
		ll maxxp=p[pl];
		ll maxxq=q[pl];
		for(int pr=pl;pr<=r;pr++){
			maxxp=max(maxxp,p[pr]);
			maxxq=max(maxxq,q[pr]);
			sum+=maxxp*maxxq;
//			printf("(%d %d) %lld\n",pl,pr,maxxp*maxxq);
		
		}
	}
}

int main(){
	freopen("match.in","r",stdin);
	freopen("macth.out","w",stdout);
	int T;
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++)
		scanf("%llu",&p[i]);
	for(int i=1;i<=n;i++)
		scanf("%llu",&q[i]);
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d",&l,&r);
		solve();
		printf("%llu\n",sum);
	}

	return 0;
}
