#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int M=250010;
int a[M],b[M];
int pa[M],pb[M];
ll val[3010][3010];
//ll sum[3010][3010];
struct Node
{
	int l,r;
	ll dat;
}ta[M*4],tb[M*4];
void abuild(int x,int l,int r)
{
	ta[x].l=l;ta[x].r=r;
	if(l>=r)
	{
		ta[x].dat=a[l];
		return;
	}
	int mid=(l+r)>>1;
	abuild(x*2,l,mid);
	abuild(x*2+1,mid+1,r);
	ta[x].dat=max(ta[x*2].dat,ta[x*2+1].dat);
}
void bbuild(int x,int l,int r)
{
	tb[x].l=l;tb[x].r=r;
	if(l>=r)
	{
		tb[x].dat=b[l];
		return;
	}
	int mid=(l+r)>>1;
	bbuild(x*2,l,mid);
	bbuild(x*2+1,mid+1,r);
	tb[x].dat=max(tb[x*2].dat,tb[x*2+1].dat);
}
ll aska(int x,int l,int r)
{
	if(l<=ta[x].l&&ta[x].r<=r)return ta[x].dat;
	int mid=(ta[x].l+ta[x].r)>>1;
	ll val=0;
	if(l<=mid)val=max(val,aska(x*2,l,r));
	if(r>mid)val=max(val,aska(x*2+1,l,r));
	return val;
}
ll askb(int x,int l,int r)
{
	if(l<=tb[x].l&&tb[x].r<=r)return tb[x].dat;
	int mid=(tb[x].l+tb[x].r)>>1;
	ll val=0;
	if(l<=mid)val=max(val,askb(x*2,l,r));
	if(r>mid)val=max(val,askb(x*2+1,l,r));
	return val;
}
ll res[3010][3010];
ll sum[3010][3010];
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T,n,q;
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),pa[a[i]]=i;
	for(int i=1;i<=n;++i)scanf("%d",&b[i]),pb[b[i]]=i;
	scanf("%d",&q);
	abuild(1,1,n);
	bbuild(1,1,n);
	for(int l=1;l<=n;++l)
	{
		for(int r=l;r<=n;++r)
		{
			val[l][r]=aska(1,l,r)*askb(1,l,r);
		}
	}
	for(int l=1;l<=n;++l)
	{
		for(int r=l;r<=n;++r)
			sum[l][r]=sum[l][r-1]+val[l][r];
	}
	for(int r=1;r<=n;++r)
	{
		for(int l=r;l>=1;--l)
		{
			res[l][r]=res[l+1][r]+sum[l][r];
		}
	}
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%llu\n",res[l][r]);
		continue;
	}
	return 0;
}
