#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define pa pair<long long,long long>
#define mp make_pair
#define fi first
#define se second

const int N=250005;
struct query{
	int id,x,y,k;
}q[N];
int T,n,Q,tmp=1,m1,m2,i,j,pos,size,L,R;
int pre1[N],pre2[N],nxt1[N],nxt2[N],pos1[N],pos2[N],lg[N],f1[N][21],f2[N][21],order[N];
ull ans,s,va,vb;
ull a[N],b[N],v1[N],v2[N],v3[N],pt[N];
stack<int>stk;
bool ex[N];
inline ull read(){
	ull x=0;register char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return x;
}
bool cmp(query x,query y){
	if(x.k==y.k){
		if(x.y==y.y) return x.x<y.x;
	    return x.y*order[x.k]<y.y*order[y.k];
	}
	return x.k<y.k;
}
void ST(){
	int l=2;
	for(i=2;i<=n;++i) if(i&l) lg[i]=lg[i-1]+1,l<<=1;else lg[i]=lg[i-1];
	for(i=1;i<=n;++i) f1[i][0]=a[i],f2[i][0]=b[i];
	for(j=1;j<=lg[n];++j)
	    for(i=1;i+(1<<j)-1<=n;++i){
	        f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
	        f2[i][j]=max(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
	    }
}
int qry1(int x,int y){
	int z=lg[y-x+1];
	return max(f1[x][z],f1[y-(1<<z)+1][z]);
}
int qry2(int x,int y){
	int z=lg[y-x+1];
	return max(f2[x][z],f2[y-(1<<z)+1][z]);
}
ull expl(int x,int r){
	//left x+1->x
	m1=qry1(x,r);m2=qry2(x,r);
	pos=max(pos1[m1],pos2[m2]);
	s=(r-pos+1)*m1*m2;
	j=x;va=vb=0;
	while(j<pos){
		va=max(va,a[j]);vb=max(vb,b[j]);
		s+=va*vb*(min(nxt1[j],nxt2[j])-j),j=min(nxt1[j],nxt2[j]);
	}
	return s;
}
ull expr(int l,int x){
	//right x-1->x
	m1=qry1(l,x);m2=qry2(l,x);
	pos=min(pos1[m1],pos2[m2]);
	s=(pos-l+1)*m1*m2;
	j=x;va=vb=0;
	while(j>pos){
		va=max(va,a[j]);vb=max(vb,b[j]);
		s+=va*vb*(j-max(pre1[j],pre2[j])),j=max(pre1[j],pre2[j]);
	}
	return s;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();n=read();
	for(i=1;i<=n;++i) a[i]=read(),pos1[a[i]]=i;
	for(i=1;i<=n;++i) b[i]=read(),pos2[b[i]]=i;
	size=floor(sqrt(n));
	Q=read();
	for(i=1;i<=Q;++i){
		q[i].id=i;
		q[i].x=read();q[i].y=read();
		q[i].k=(q[i].x-1)/size;
		ex[q[i].k]=true;
	}
	for(i=0;i<=n/size;++i)
	    if(ex[i]){
	    	order[i]=tmp;
	    	tmp=-tmp;
	    }
	sort(q+1,q+Q+1,cmp);
	ST();
	
	for(i=1;i<=n;++i){
		while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
		if(stk.empty()) pre1[i]=0;else pre1[i]=stk.top();
		stk.push(i);
		v1[i]=v1[pre1[i]]+a[i]*(i-pre1[i]);
	}
	while(!stk.empty()) stk.pop();
	for(i=1;i<=n;++i){
		while(!stk.empty()&&b[stk.top()]<b[i]) stk.pop();
		if(stk.empty()) pre2[i]=0;else pre2[i]=stk.top();
		stk.push(i);
		v2[i]=v2[pre2[i]]+b[i]*(i-pre2[i]);
	}
	while(!stk.empty()) stk.pop();
	for(i=n;i>0;--i){
		while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
		if(stk.empty()) nxt1[i]=n+1;else nxt1[i]=stk.top();
		stk.push(i);
		//v1[i]=v1[pre1[i]]+a[i]*(i-pre1[i]);
	}
	while(!stk.empty()) stk.pop();
	for(i=n;i>0;--i){
		while(!stk.empty()&&b[stk.top()]<b[i]) stk.pop();
		if(stk.empty()) nxt2[i]=n+1;else nxt2[i]=stk.top();
		stk.push(i);
		//v2[i]=v2[pre2[i]]+b[i]*(i-pre2[i]);
	}
	
	L=R=q[1].x;ans=a[q[1].x]*b[q[1].x];
	for(i=1;i<=Q;++i){
		while(L<q[i].x) ans-=expl(L,R),++L;
		while(L>q[i].x) --L,ans+=expl(L,R);
		while(R<q[i].y) ++R,ans+=expr(L,R);
		while(R>q[i].y) ans-=expr(L,R),--R;
		pt[q[i].id]=ans;
	}
	for(i=1;i<=Q;++i)
	    printf("%lld\n",pt[i]);
	return 0;
}
