#include<bits/stdc++.h>
using namespace std;
const long long N=250005;
unsigned long long a[N],b[N],ans[N],ma,mb;
long long n,T,Q,l[N],r[N],ml,mr;
long long read() {
	long long x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);

	scanf("%lld%lld",&T,&n);
	for (int i=1;i<=n;i++)
		a[i]=read();
	for (int i=1;i<=n;i++)
		b[i]=read();
	scanf("%lld",&Q);
	if (n<=3000||Q<=5) {
		for (int k=1;k<=Q;k++) {
			scanf("%lld%lld",&l[0],&r[0]);
			ans[0]=0;
			for (int i=l[0];i<=r[0];++i) {
				ma=0; mb=0;
				for (int j=i;j<=r[0];++j) {
					ma=max(ma,a[j]);
					mb=max(mb,b[j]);
					ans[0]=ans[0]+ma*mb;
				}
			}
			printf("%lld\n",ans[0]);
		}
	} else {
		for (int k=1;k<=Q;k++) {
			scanf("%lld%lld",&l[k],&r[k]);
			if (ml==0) ml=l[k];
			ml=min(ml,l[k]);
			mr=max(mr,r[k]);
		}
		for (int i=ml;i<=mr;i++) {
			for (int j=i;j<=mr;j++) {
				ma=max(ma,a[j]);
				mb=max(mb,b[j]);
				for (int k=1;k<=Q;k++)
					if (l[k]<=i&&r[k]>=j)
						ans[k]=ans[k]+ma*mb;
			}
		}	
		for (int i=1;i<=Q;i++)
			printf("%lld\n",ans[i]);
	}
	return 0;
}