#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=250050;
int n,i,j,k,p,m,l,r,Ma,Mb;
int a[Maxn],b[Maxn],jl[3050][3050],sum[3050];
int read()
{
	int s=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		s=(s<<3)+(s<<1)+c-'0';
		c=getchar();
	}
	return s*f;
}
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(),n=read();
	for(i=1;i<=n;i++)
	{
		a[i]=read();
	}
	for(i=1;i<=n;i++)
	{
		b[i]=read();
	}
	m=read();
	if(n<=3000)
	{
		for(i=1;i<=n;i++)
		{
			Ma=0,Mb=0;
			for(j=i;j<=n;j++)
			{
				Ma=max(Ma,a[j]),Mb=max(Mb,b[j]);
				jl[i][j]=Ma*Mb,sum[j]=sum[j]+jl[i][j];
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				sum[j]=sum[j]-jl[i][j],jl[i][j]=jl[i][j]+jl[i][j-1]+sum[j];
			}
		}
		for(i=1;i<=m;i++)
		{
			l=read(),r=read();
			printf("%lld\n",jl[l][r]);
		}
	}
	else
	{
		for(i=1;i<=m;i++)
		{
			l=read(),r=read();
			p=0;
			for(j=l;j<=r;j++)
			{
				Ma=0,Mb=0;
				for(k=j;k<=r;k++)
				{
					Ma=max(Ma,a[k]),Mb=max(Mb,b[k]);
					p=p+Ma*Mb;
				}
			}
			printf("%lld\n",p);
		}
	}
	return 0;
}