#include <bits/stdc++.h>
using namespace std;
const long long mod=2e64,N=3e5;
int n,Q;
long long a[N],b[N],ans,s1[3005][3005],s2[3005][3005];
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	int T,i,j,l,r;
	
	cin>>T>>n;
	for (i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (i=1;i<=n;i++) scanf("%lld",&b[i]);
	
	cin>>Q;
if (n<=30&&Q<=30)
{
	while (Q--)
	{
		//cout<<Q<<endl;
		scanf("%d%d",&l,&r);
		{
			ans=0;
			for (i=l;i<=r;i++)
			{
				long long max1=0,max2=0;
				for (j=i;j<=r;j++) 
				{
					max1=max(max1,a[j]),max2=max(max2,b[j]);
					//if (l==7&&r==9) cout<<max1<<' '<<max2<<endl;
					ans=(ans+(max1*max2)%mod)%mod;
				}
			}
			printf("%lld\n",ans);
		}
	}
} else
{
	for (i=1;i<=n;i++)
	{
		long long max1=0,max2=0;
		for (j=i;j<=n;j++)
		{
			max1=max(max1,a[j]),max2=max(max2,b[j]);
			s1[i][j]=s1[i][j-1]+max1;
			s2[i][j]=s2[i][j-1]+max2;
		}
	}
	while (Q--)
	{
		scanf("%d%d",&l,&r);
		printf("%lld\n",s1[l][r]*s2[l][r]%mod/2);
	}
}
	
	return 0;
}
