#include<bits/stdc++.h>
using namespace std;
long long T,a[300000],b[300000],n,ma[4000][4000],mb[4000][4000],q,l,r;
unsigned long long ans;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for (int i=1;i<=n;i++)
	 cin>>a[i];
	for (int i=1;i<=n;i++)
	{
		for (int j=i;j<=n;j++)
		 ma[i][j]=max(ma[i][j-1],a[j]);
	}
	for (int i=1;i<=n;i++)
	 cin>>b[i];
	for (int i=1;i<=n;i++)
	{
		for (int j=i;j<=n;j++)
		 mb[i][j]=max(mb[i][j-1],b[j]);
	}
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		ans=0;
		cin>>l>>r;
		for (int i=l;i<=r;i++)
		 for (int j=i;j<=r;j++)
		  ans=ans+ma[i][j]*mb[i][j];
		cout<<ans<<endl;
	}
}