#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int x,y,q,t,n,max1[1001][1001],max2[1001][1001];
int a[100001],b[100001];
unsigned long long dp[1001][1001];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>t>>n;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	for (int i=1;i<=n;i++)
	{
		for (int j=i;j<=n;j++)
		{
			max1[i][j]=max(max1[i][j-1],a[j]);
			max2[i][j]=max(max2[i][j-1],b[j]);
		}
	}
	for (int i=1;i<=n;i++) dp[i][i]=max1[i][i]*max2[i][i];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;i+j<=n;j++)
		{
			dp[j][i+j]=(dp[j][i+j-1]+dp[j+1][i+j]-dp[j+1][i+j-1]+1ll*max1[j][i+j]*max2[j][i+j]);
		}
	}
//	cout<<dp[1][1]<<" "<<dp[2][2]<<" "<<dp[1][2]<<endl;
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%lld\n",dp[x][y]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
