#include<bits/stdc++.h>
using namespace std;
long long a,b,d[200001],f[200001],q,w,mx[3001][3001],mx1[3001][3001],T,nxt[3001][3001],nxt1[3001][3001];
unsigned long long an=0;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%lld%lld",&T,&a);
	for(int i=1;i<=a;i++)
	{
		scanf("%lld",&d[i]);
	}
	for(int i=1;i<=a;i++) scanf("%lld",&f[i]);
	for(int i=1;i<=a;i++)
	{
		long long la=i,la1=i;
		long long cn1=0;
		for(int j=i;j<=a;j++)
		{
			mx[i][j]=mx[i][j-1];
			mx1[i][j]=mx1[i][j-1];
			if(d[j]>mx[i][j]&&j!=i)
			{
				++cn1;
				for(int k=la;k<j;k++) nxt[i][k]=j;
				la=j;
			}
			if(f[j]>mx1[i][j]&&j!=i)
			{
				for(int k=la1;k<j;k++) nxt1[i][k]=j;
				la1=j;
			}
			mx[i][j]=max(mx[i][j-1],d[j]);
			mx1[i][j]=max(mx1[i][j-1],f[j]);
		}
		for(int k=la;k<=a;k++) nxt[i][k]=a+1;
		for(int k=la1;k<=a;k++) nxt1[i][k]=a+1;
	}
	scanf("%lld",&b);
	for(int i=1;i<=b;i++)
	{
		scanf("%lld%lld",&q,&w);an=0;
		for(int j=w;j>=q;j--)
		{
			long long t1=j,t2=j;
			for(int k=j;k<=w;k++)
			{
				long long tt=min(nxt[j][k],nxt1[j][k]);
				tt=min(tt,w+1);
				an+=mx[j][k]*mx1[j][k]*(tt-k);k=tt-1;
			}
		}
		cout<<an<<"\n";
	}
	return 0;
}