#include<bits/stdc++.h>
using namespace std;
int n,a[250005],b[250005],la[250005],ra[250005],lb[250005],rb[250005];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int t;
	scanf("%d%d",&t,&n);
	a[0]=a[n+1]=b[0]=b[n+1]=n+1;
	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++){
		la[i]=i;
		while(a[i]>a[la[i]-1]) la[i]=la[la[i]-1];
		lb[i]=i;
		while(b[i]>b[lb[i]-1]) lb[i]=lb[lb[i]-1];
	}
	for(int i=n;i;i--){
		ra[i]=i;
		while(a[i]>a[ra[i]+1]) ra[i]=ra[ra[i]+1];
		rb[i]=i;
		while(b[i]>b[rb[i]+1]) rb[i]=rb[rb[i]+1];
	}
	scanf("%d",&t);
	while(t--){
		int l,r;
		scanf("%d%d",&l,&r);
		unsigned long long ans=0;
		for(int p=l;p<=r;p++)
			for(int q=p;q<=r;q++){
				unsigned long long ma=0,mb=0;
				for(int i=p;i<=q;i++)
					ma=a[i]>ma?a[i]:ma,
					mb=b[i]>mb?b[i]:mb;
				ans+=ma*mb;
			}
		printf("%llu\n",ans);
	}
	return 0;
}