#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>

const int Maxn=5e5+7;

typedef unsigned long long ULL;

int a[Maxn],b[Maxn];
int n,q,lg[Maxn],sta[Maxn][25],stb[Maxn][25];
ULL res;

ULL calc(ULL x)
{
	if(x&1)
		return ((x-1)>>1)*x;
	return (x>>1)*(x-1);
}

void build(int a[],int st[][25])
{
	for(int i=1;i<=n;++i)
		st[i][0]=a[i];

	for(int j=1;j<=lg[n];++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			st[i][j]=std::max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int query(int l,int r,int st[][25])
{
	int k=lg[r-l+1];
	return std::max(st[l][k],st[r-(1<<k)+1][k]);
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	scanf("%*d%d",&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=2;i<=n;++i)
		lg[i]=lg[i>>1]+1;
	
/*	build(a);
	
	for(int i=1;i<=n;++i)
	{
		int l=1,r=i;
		
		while(l<=r)
		{
			int mid=(l+r)>>1;
			
			if(query(mid,i)>a[i])
				l=mid+1;
			else
				r=mid-1;
		}
		
		al[i]=l;
	}
	
	for(int i=n;i>=1;--i)
	{
		int l=i,r=n;
		
		while(l<=r)
		{
			int mid=(l+r)>>1;
			
			if(query(i,mid)>a[i])
				r=mid-1;
			else
				l=mid+1;
		}
		ar[i]=l-1;
	}
	for(int i=1;i<=n;++i)
		printf("%d %d\n",al[i],ar[i]);*/
	
	
	build(a,sta);
	build(b,stb);
/*
	for(int i=1;i<=n;++i)
	{
		int l=1,r=i;
		
		while(l<=r)
		{
			int mid=(l+r)>>1;
			
			if(query(mid,i)>b[i])
				l=mid+1;
			else
				r=mid-1;
		}
		
		bl[i]=l;
	}
	
	for(int i=n;i>=1;--i)
	{
		int l=i,r=n;
		
		while(l<=r)
		{
			int mid=(l+r)>>1;
			
			if(query(i,mid)>b[i])
				r=mid-1;
			else
				l=mid+1;
		}
		
		br[i]=l-1;
	}*/

	scanf("%d",&q);
	
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		
		for(int p=l;p<=r;++p)
			for(int q=p;q<=r;++q)
				res+=1ULL*query(p,q,sta)*query(p,q,stb);
		
		printf("%llu\n",res);
	}
}