//妹子when???
#include<bits/stdc++.h>
#define pb push_back
#define pc putchar
#define fi first
#define se second
#define eb emplace_back
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define mp make_pair
#define mt make_tuple
using namespace std;
typedef unsigned long long ull;
template<class T>void read(T&x){
	char c=getchar();bool f=0;x=0;
	for(;!isdigit(c);c=getchar())if(c=='-')f=1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	if(f)x=-x;
}
template<class T,class ...Arg>void read(T&x,Arg&...arg){read(x);read(arg...);}
template<class T>void write(T x){
	if(x<0)x=-x,pc('-');
	if(x>=10)write(x/10);
	pc(x%10+'0');
}
template<class T,class ...Arg>void write(T x,Arg ...arg){write(x);pc(' ');write(arg...);}
template<class ...Arg>void writeln(Arg ...arg){write(arg...);pc('\n');}
const int N=2.5e5+10;
int T,n,a[N],b[N],q,l[N],r[N];
namespace solve0{
	const int N=3e3+10;
	int amx[N][N],bmx[N][N];
	ull res[N][N];
	void work(){
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				amx[i][j]=max(amx[i][j-1],a[j]),
				bmx[i][j]=max(bmx[i][j-1],b[j]);
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				res[i][j]=res[i][j-1]+ull(amx[i][j])*bmx[i][j];
		for(int len=1;len<=n;len++)
			for(int i=1,j=len;j<=n;i++,j++)
				res[i][j]+=res[i+1][j];
		for(int i=1;i<=q;i++)writeln(res[l[i]][r[i]]);
	}
}
namespace solve1{
	struct SGT{
		ull a[N<<2],b[N<<2];int tg[N<<2];
		void pushup(int x){
			a[x]=a[lc]+a[rc];
			b[x]=b[lc]+b[rc];
		}
		void pushtag(int x,int v){
			b[x]+=v*a[x];
			tg[x]+=v;
		}
		void pushdown(int x){
			if(tg[x]){
				pushtag(lc,tg[x]);
				pushtag(rc,tg[x]);
				tg[x]=0;
			}
		}
		void upd(int x,int l,int r,int p,ull v){
			if(l==r)return a[x]=v,void();
			pushdown(x);
			if(p<=mid)upd(lc,l,mid,p,v);
			else upd(rc,mid+1,r,p,v);
			pushup(x);
		}
		ull qry(int x,int l,int r,int qr){
			if(qr<l)return 0;
			if(r<=qr)return b[x];
			pushdown(x);
			return qry(lc,l,mid,qr)+qry(rc,mid+1,r,qr);
		}
	}T;
	int stA[N],topA,stB[N],topB;
	vector<int>qry[N];
	int A[N],B[N];ull ans[N];
	void work(){
		for(int i=1;i<=q;i++)qry[l[i]].pb(i);
		stA[0]=stB[0]=n+1;
		for(int i=n;i;i--){
			while(topA&&a[stA[topA]]<a[i])topA--;
			while(topB&&b[stB[topB]]<b[i])topB--;
			for(int j=i;j<stA[topA];j++)A[j]=a[i];
			for(int j=i;j<stB[topB];j++)B[j]=b[i];
			for(int j=i;j<stA[topA]||j<stB[topB];j++)T.upd(1,1,n,j,ull(A[j])*B[j]);
			stA[++topA]=stB[++topB]=i;T.pushtag(1,1);
			for(auto id:qry[i])ans[id]=T.qry(1,1,n,r[id]);
		}
		for(int i=1;i<=q;i++)writeln(ans[i]);
	}
}
namespace solve2{
	struct node{
		ull suma,sumb,sumab,sumc;
		int len;
	};
	struct tag{
		int taga,tagb;
		ull a,b,c,d;
		void clear(){taga=tagb=0;a=b=c=d=0;}
	};
	bool operator==(node X,node Y){
		return X.suma==Y.suma&&X.sumb==Y.sumb&&X.sumab==Y.sumab&&X.sumc==Y.sumc;
	}
	node operator+(node X,node Y){
		node res;
		res.suma=X.suma+Y.suma;
		res.sumb=X.sumb+Y.sumb;
		res.sumab=X.sumab+Y.sumab;
		res.sumc=X.sumc+Y.sumc;
		res.len=X.len+Y.len;
		return res;
	}
	node operator+(node X,tag Y){
		node res=X;
		if(Y.taga)res.suma=ull(Y.taga)*X.len;
		if(Y.tagb)res.sumb=ull(Y.tagb)*X.len;
		if(Y.taga&&Y.tagb)res.sumab=ull(Y.taga)*Y.tagb*X.len;
		else if(Y.taga)res.sumab=ull(Y.taga)*X.sumb;
		else if(Y.tagb)res.sumab=ull(Y.tagb)*X.suma;
		res.sumc+=Y.a*X.suma+Y.b*X.sumb+Y.c*X.sumab+Y.d*X.len;
		return res;
	}
	tag operator+(tag X,tag Y){
		tag res=X;
		if(Y.taga)res.taga=Y.taga;
		if(Y.tagb)res.tagb=Y.tagb;
		res.d+=Y.d;
		if(X.taga)res.d+=X.taga*Y.a;
		else res.a+=Y.a;
		if(X.tagb)res.d+=X.tagb*Y.b;
		else res.b+=Y.b;
		if(X.taga&&X.tagb)res.d+=ull(X.taga)*X.tagb*Y.c;
		else if(X.taga)res.b+=ull(X.taga)*Y.c;
		else if(X.tagb)res.a+=ull(X.tagb)*Y.c;
		else res.c+=Y.c;
		return res;
	}
	node v[N<<2];tag t[N<<2],now;
	void build(int x,int l,int r){
		if(l==r)return v[x].len=1,void();
		build(lc,l,mid);build(rc,mid+1,r);
		v[x]=v[lc]+v[rc];
	}
	void pushtag(int x,tag&T){
		v[x]=v[x]+T;
		t[x]=t[x]+T;
	}
	void pushdown(int x){
		pushtag(lc,t[x]);
		pushtag(rc,t[x]);
		t[x].clear();
	}
	void upd(int x,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return pushtag(x,now);
		if(r<ql||qr<l)return;
		pushdown(x);
		upd(lc,l,mid,ql,qr);upd(rc,mid+1,r,ql,qr);
		v[x]=v[lc]+v[rc];
	}
	ull qry(int x,int l,int r,int qr){
		if(r<=qr)return v[x].sumc;
		if(qr<l)return 0;
		pushdown(x);
		return qry(lc,l,mid,qr)+qry(rc,mid+1,r,qr);
	}
	int stA[N],topA,stB[N],topB;
	vector<int>qrys[N];
	int A[N],B[N];ull ans[N];
	void work(){
		for(int i=1;i<=q;i++)qrys[l[i]].pb(i);
		stA[0]=stB[0]=n+1;build(1,1,n);
		
		for(int i=n;i;i--){
			while(topA&&a[stA[topA]]<a[i])topA--;
			while(topB&&b[stB[topB]]<b[i])topB--;
			now={a[i],0,0,0,0,0};upd(1,1,n,i,stA[topA]-1);
			now={0,b[i],0,0,0,0};upd(1,1,n,i,stB[topB]-1);
			now={0,0,0,0,1,0};upd(1,1,n,1,n);
			stA[++topA]=stB[++topB]=i;
			for(auto id:qrys[i])ans[id]=qry(1,1,n,r[id]);
		}
		for(int i=1;i<=q;i++)writeln(ans[i]);
	}
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(T,n);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++)read(b[i]);
	read(q);
	for(int i=1;i<=q;i++)read(l[i],r[i]);
	if(n<=3e3)solve0::work();
	//else solve1::work();
	else solve2::work();
	return 0;
}
