#include<bits/stdc++.h>
using namespace std;
int t,n,a[250011],b[250011],l,r,sta[65537][20],stb[65537][20],er[20],ppp[65537];
unsigned long long ans,maxa,maxb;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&t,&n);
	er[0]=1;
	for(int i=1;i<=15;i++) er[i]=er[i-1]*2,ppp[er[i]]=1;
	ppp[1]=0;
	for(int i=2;i<=er[15];i++) ppp[i]=ppp[i]+ppp[i-1];
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) sta[i][0]=a[i],stb[i][0]=b[i];
	for(int i=1;i<=14;i++) for(int j=1;j<=n;j++) sta[j][i]=max(sta[j][i-1],sta[j+er[i-1]][i-1]);
	for(int i=1;i<=14;i++) for(int j=1;j<=n;j++) stb[j][i]=max(stb[j][i-1],stb[j+er[i-1]][i-1]);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&l,&r);
		ans=0;
		for(int p=l;p<=r;p++)
			for(int q=p;q<=r;q++)
			{
				maxa=max(sta[p][ppp[q-p]],sta[q-er[ppp[q-p]]+1][ppp[q-p]]);
				maxb=max(stb[p][ppp[q-p]],stb[q-er[ppp[q-p]]+1][ppp[q-p]]);
				ans=ans+maxa*maxb;
			}
		printf("%u\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}