#include <bits/stdc++.h>
using namespace std;
#define ull  unsigned long long
int T,n;
ull a[300300],b[300300],Max1[3003][3003],Max2[3003][3003];
int Q;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&T,&n);
	for (int i=1;i<=n;i++)scanf("%u",&a[i]);
	for (int i=1;i<=n;i++)scanf("%u",&b[i]);
	for (int i=1;i<=n;i++)
	{
		ull max1=-INT_MAX;
		for (int j=i;j<=n;j++)
		{
			max1=max(max1,a[j]);
			Max1[i][j]=max1;
		}
	}
	for (int i=1;i<=n;i++)
	{
		ull max2=-INT_MAX;
		for (int j=i;j<=n;j++)
		{
			max2=max(max2,b[j]);
			Max2[i][j]=max2;
		}
	}
	scanf("%d",&Q);
	while (Q--)
	{
		
		int l,r;
		scanf("%d%d",&l,&r);
		unsigned long long res=0;
		for (int i=l;i<=r;i++)
		{
			for (int j=i;j<=r;j++)
			{
				if ((unsigned long long)(res-(2<<63)+(Max1[i][j]*Max2[i][j])-(2<<63))>=0)
					res=res-(2<<63)+(Max1[i][j]*Max2[i][j])-(2<<63);
				else
					res+=Max1[i][j]*Max2[i][j];
			}
		}
		printf("%u\n",res);
	}
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/