#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const int N=3e5+5;
struct node{
	u64 ssum,sumX,sumY,sumXY;
	int tagX,tagY;
}d[N*4];
int T,n,m,a[N],b[N],posA[N],posB[N];
u64 ans[N];
vector<pair<int,int> >vq[N];
inline void cover_x(int o,int len,int v){
	d[o].tagX=v;
	d[o].sumX=(u64)len*(u64)v;
	d[o].sumXY=(u64)v*d[o].sumY;
}
inline void cover_y(int o,int len,int v){
	d[o].tagY=v;
	d[o].sumY=(u64)len*(u64)v;
	d[o].sumXY=(u64)v*d[o].sumX;
}
inline void pushdown(int o,int len){
	if(int&x=d[o].tagX){
		cover_x(o<<1,(len+1)/2,x);
		cover_x(o<<1|1,len/2,x);
		x=0;
	}
	if(int&y=d[o].tagY){
		cover_y(o<<1,(len+1)/2,y);
		cover_y(o<<1|1,len/2,y);
		y=0;
	}
}
inline void update(int o){
	d[o].sumX=d[o<<1].sumX+d[o<<1|1].sumX;
	d[o].sumY=d[o<<1].sumY+d[o<<1|1].sumY;
	d[o].sumXY=d[o<<1].sumXY+d[o<<1|1].sumXY;
}
void coverX(int l,int r,int o,const int&L,const int&R,const int&v){
	if(L<=l&&r<=R){
		cover_x(o,r-l+1,v);
		return;
	}
	pushdown(o,r-l+1);
	const int mid=(l+r)/2;
	if(L<=mid)coverX(l,mid,o<<1,L,R,v);
	if(mid<R)coverX(mid+1,r,o<<1|1,L,R,v);
	update(o);
}
void coverY(int l,int r,int o,const int&L,const int&R,const int&v){
	if(L<=l&&r<=R){
		cover_y(o,r-l+1,v);
		return;
	}
	pushdown(o,r-l+1);
	const int mid=(l+r)/2;
	if(L<=mid)coverY(l,mid,o<<1,L,R,v);
	if(mid<R)coverY(mid+1,r,o<<1|1,L,R,v);
	update(o);
}
u64 query(int l,int r,int o,const int&L,const int&R){
	if(L<=l&&r<=R)return d[o].sumXY;
	pushdown(o,r-l+1);
	const int mid=(l+r)/2;
	u64 res=0;
	if(L<=mid)res=query(l,mid,o<<1,L,R);
	if(mid<R)res+=query(mid+1,r,o<<1|1,L,R);
	return res;
}
void work(){
	static int staA[N],staB[N];
	int topA=0,topB=0;
	staA[0]=staB[0]=n+1;
	for(int i=n;i;--i){
		while(topA&&a[staA[topA]]<a[i])--topA;
		coverX(1,n,1,i,staA[topA]-1,a[i]);
		staA[++topA]=i;
		while(topB&&b[staB[topB]]<b[i])--topB;
		coverY(1,n,1,i,staB[topB]-1,b[i]);
		staB[++topB]=i;
		for(auto it:vq[i])
			ans[it.second]+=query(1,n,1,i,it.first);
	}
}
void work1(){
	static u64 res[3005][3005];
	for(int i=n;i;--i){
		u64 mxa=0,mxb=0;
		for(int j=i;j<=n;++j){
			mxa=max(mxa,(u64)a[j]);
			mxb=max(mxb,(u64)b[j]);
			res[i][j]=res[i+1][j]+res[i][j-1]-res[i+1][j-1]+mxa*mxb;
		}
	}
	for(int i=1;i<=m;++i){
		int l,r;
		cin>>l>>r;
		ans[i]=res[l][r];
	}
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T>>n;
	for(int i=1;i<=n;++i)cin>>a[i],posA[a[i]]=i;
	for(int i=1;i<=n;++i)cin>>b[i],posB[b[i]]=i;
	cin>>m;
	if(n<=3000&&m<=3000)work1();
	else if(m<=5){
		for(int i=1;i<=m;++i){
			int l,r;
			cin>>l>>r;
			for(int j=l;j<=r;++j)
				vq[j].emplace_back(r,i);
		}
		work();
	}
	for(int i=1;i<=m;++i)
		cout<<ans[i]<<'\n';
	return 0;
}
