#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int maxn=1e6+7;
int read()
{
	int res=0,f=1;
	char c=getchar();
	while(c!='-' && !isdigit(c)) c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(isdigit(c)) res=res*10+c-48,c=getchar();
	return res*f;
}
ull a[maxn],b[maxn];
ull f[3010][3010];
void sub()
{
	int q=read();
	while(q--)
	{
		int l=read(),r=read();
		ull ans=0;
		for(int i=l;i<=r;i++)
		{
			ull Mx1=0,Mx2=0;
			for(int j=i;j<=r;j++)
			{
				Mx1=max(Mx1,a[j]);
				Mx2=max(Mx2,b[j]);
				ans+=(Mx1*Mx2);
			}
		}
		cout<<ans<<endl;
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int id=read(),n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int j=1;j<=n;j++) b[j]=read();
	if(n>3000) 
	{
		sub();
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		ull Mx1=0,Mx2=0;
		for(int j=i;j<=n;j++)
		{
			Mx1=max(Mx1,a[j]);
			Mx2=max(Mx2,b[j]);
			f[i][j]=(Mx1*Mx2);
		}
	}
	for(int i=n-1;i;i--)
		for(int j=i;j<=n;j++)
			f[i][j]+=f[i+1][j];
	int q=read();
	while(q--)
	{
		int l=read(),r=read();
		ull ans=0;
		for(int j=l;j<=r;j++)
			ans+=f[l][j];
//		for(int i=l;i<=r;i++)
//		{
//			ull Mx1=0,Mx2=0;
//			for(int j=i;j<=r;j++)
//			{
//				Mx1=max(Mx1,a[j]);
//				Mx2=max(Mx2,b[j]);
//				ans+=(Mx1*Mx2);
//			}
//		}
		cout<<ans<<endl;
	}
	return 0;
}