#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=3010;

int T,n,x,y;
ll a[N],b[N],ret,s[N][N],mx1,mx2;

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&T,&n);
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for (int i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	for (int i=1;i<=n;i++)
	{
		mx1=mx2=0;
		for (int j=i;j<=n;j++)
		{
			mx1=max(mx1,a[j]);
			mx2=max(mx2,b[j]);
			s[i][j]=s[i][j-1]+mx1*mx2;
//			cout<<i<<"   "<<j<<"   "<<s[i][j]<<endl;
		}
	}
	for (int j=n;j>=1;j--)
	{
		for (int i=j-1;i>=1;i--)
		{
			s[i][j]+=s[i+1][j];
//			cout<<i<<"   "<<j<<"   "<<s[i][j]<<endl;
		}
	}
	int Q;
	scanf("%d",&Q);
	while (Q--)
	{
		ret=0;
		scanf("%d%d",&x,&y);
		cout<<s[x][y]<<endl;
//		printf("%ull\n",s[x][y]);
	}
	return 0;
}