#include<bits/stdc++.h>
using namespace std;
int n,T,Q;
unsigned long long ans[3009],d;
long long mxa[3009][3009],mxb[3009][3009],a[3009],b[3009];
int main()
{
	//freopen("match.in","r",stdin);
	//freopen("match.out","w",stdout);
	scanf("%d%d",&T,&n);
	for(int r=1;r<=n;r++)
	{
		scanf("%lld",&a[r]);
		for(int l=r;l>=1;l--)
		{
			mxa[l][r]=max(mxa[l+1][r],a[l]);
		}
	}
	for(int r=1;r<=n;r++)
	{
		scanf("%lld",&b[r]);
		for(int l=r;l>=1;l--)
		{
			mxb[l][r]=max(mxb[l+1][r],b[l]);
		}
	}
	scanf("%d",&Q);
	int x,y;
	for(int i=1;i<=Q;i++)
	{	
	    d=0;
		scanf("%d%d",&x,&y);
		for(int l=x;l<=y;l++)
		{
			for(int r=l;r<=y;r++)
			{
				d+=mxa[l][r]*mxb[l][r];
			}
		}
		cout<<d<<endl;
	}
	return 0;
}