#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
int n,T,A[MAXN],B[MAXN],mx[40][40][2];
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("%d",&A[i]);
	for(int i=1;i<=n;++i) scanf("%d",&B[i]);
	for(int i=1;i<=n;++i)
	{
		int mxx=A[i];
		for(int j=i;j<=n;++j)
		{
			mxx=max(A[j],mxx);
			mx[i][j][0]=mxx;
		}
		mxx=B[i];
		for(int j=i;j<=n;++j)
		{
			mxx=max(B[j],mxx);
			mx[i][j][1]=mxx;
		}
	}
	int Q;scanf("%d",&Q);
	while(Q--)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		unsigned long long Ans=0;
		for(int i=l;i<=r;++i)
			for(int j=i;j<=r;++j)
				Ans+=mx[i][j][0]*mx[i][j][1];
		printf("%llu\n",Ans);		
	}
	return 0;
}
