#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
constexpr int max_n=250000;
unsigned int a[max_n+1],anxt[max_n+1],b[max_n+1],bnxt[max_n+1];
int stk[max_n+1];
ull deal(int l,const int r){
	ull x=a[l],y=b[l],ans=0;
	int p=min(anxt[l],bnxt[l]);
	while(p<=r){
		ans+=x*y*(p-l);
		l=p;
		if(a[l]>x)
			x=a[l];
		if(b[l]>y)
			y=b[l];
		p=min(anxt[l],bnxt[l]);
	}
	ans+=x*y*(r-l+1);
	return ans;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int t,n;
	scanf("%d%d",&t,&n);
	for(int i=1; i<=n; ++i)
		scanf("%u",a+i);
	for(int j=1; j<=n; ++j)
		scanf("%u",b+j);
	int top=0;
	stk[0]=n+1;
	for(int i=n; i; --i){
		const int v=a[i];
		while(top&&v>=a[stk[top]])
			--top;
		anxt[i]=stk[top];
		stk[++top]=i;
	}
	top=0;
	for(int i=n; i; --i){
		const int v=b[i];
		while(top&&v>=b[stk[top]])
			--top;
		bnxt[i]=stk[top];
		stk[++top]=i;
	}
	int q;
	scanf("%d",&q);
	for(int i=1,l,r; i<=q; ++i){
		scanf("%d%d",&l,&r);
		ull ans=0;
		for(int i=l; i<=r; ++i)
			ans+=deal(i,r);
		printf("%llu\n",ans);
	}
	return 0;
}