#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=3005;
int id,n,q;
int a[maxn],b[maxn];
int ma[maxn][maxn],mb[maxn][maxn];
void rd(int &rex)
{
	char c=getchar();int f=1;rex=0;
	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while(c>='0'&&c<='9')rex=rex*10+c-'0',c=getchar();
	rex*=f;
}
int main()
{
	freopen("match.in","r",stdin); freopen("match.out","w",stdout);
	rd(id);rd(n);
	for(int i=1;i<=n;i++)rd(a[i]);
	for(int j=1;j<=n;j++)rd(b[j]);
	rd(q);
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	ma[i][j]=max(ma[i][j-1],a[j]),mb[i][j]=max(mb[i][j-1],b[j]);
	while(q--)
	{
		int l,r;LL ans=0;rd(l);rd(r);
		for(int i=l;i<=r;i++)
		for(int j=l;j<=r;j++)ans+=ma[i][j]*mb[i][j];
		printf("%lld\n",ans);
	}
	return 0;
}/**/