#include<cstdio>
#include<iostream>
#include<iostream>
using namespace std;

#define ull unsigned long long
#define N 250005
int T,n,Q;
ull a[N],b[N],max1,max2;
ull ans,sum[3005][3005];
void work1()
{
	while (Q--){
		int l,r;
		scanf("%d%d",&l,&r);
		ans=0;
		for (int p=l ; p<=r ; p++){
			max1=0,max2=0;
			for (int q=p ; q<=r ; q++){
				max1=max(max1,a[q]);
				max2=max(max2,b[q]);
				ans+=max1*max2;
			}
		}
		printf("%llu\n",ans);
	}
}
void work2()
{
	memset(sum,0,sizeof(sum));
	for (int p=1 ; p<=n ; p++){
		max1=0,max2=0;
		for (int q=p ; q<=n ; q++){
			max1=max(max1,a[q]);
			max2=max(max2,b[q]);
			sum[p][q]=sum[p][q-1]+max1*max2;
		}
	}
	while (Q--){
		int l,r;
		scanf("%d%d",&l,&r);
		ans=0;
		for (int p=l ; p<=r ; p++){
			ans+=sum[p][r];
		}
		printf("%llu\n",ans);
	}
}
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("%lld",&a[i]);
	for (int i=1 ; i<=n ; i++)
	    scanf("%lld",&b[i]);
	scanf("%d",&Q);
	if (n<=30) work1();
	else work2();
	return 0;
}