#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=2.5e5+10;
ll s[3010][3010],a[N],b[N];int T,n,q;
namespace pt20
{
	void solve()
	{
		for(int i=1;i<=n;i++)
		{
			ll maxa=0,maxb=0;
			for(int j=i;j<=n;j++)
			{
				maxa=max(maxa,a[j]);
				maxb=max(maxb,b[j]);
				s[i][j]=maxa*maxb;
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		scanf("%d",&q);
		while(q--)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			printf("%llu\n",s[r][r]+s[l-1][l-1]-s[l-1][r]-s[r][l-1]);
		}
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d %d",&T,&n);
	for(int i=1;i<=n;i++)
		scanf("%llu",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%llu",&b[i]);
	if(n<=3000) pt20::solve();
}
