#include<bits/stdc++.h>
#define pb push_back
template<typename _Tp>void read(_Tp &x){
	char ch(getchar());bool f=0;while(!isdigit(ch))f|=ch=='-',ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
	if(f)x=-x;
}
const int N=250005,NC=(1<<19)+5;typedef unsigned long long ull;
int a[N],b[N];ull ans[N];
struct qry{int l,id;};
std::vector<qry> vec[N];
int st1[N],st2[N],top1,top2;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int len[NC];ull sa[NC],sb[NC],sab[NC],taga[NC],tagb[NC],val[NC],tab[NC],ta[NC],tb[NC],t[NC];
inline void pushup(int u){
	sa[u]=sa[ls(u)]+sa[rs(u)],sb[u]=sb[ls(u)]+sb[rs(u)],sab[u]=sab[ls(u)]+sab[rs(u)];
}
void build(int l,int r,int u){
	len[u]=r-l+1;if(l==r)return;
	int mid=(l+r)>>1;build(l,mid,ls(u)),build(mid+1,r,rs(u));
}
inline void upda(int x,ull C){
	sa[x]=C*len[x],sab[x]=C*sb[x],taga[x]=C;
}
inline void updb(int x,ull C){
	sb[x]=C*len[x],sab[x]=C*sa[x],tagb[x]=C;
}
inline void updd0(int x,ull C){
	val[x]+=C*len[x],t[x]+=C;
}
inline void updda(int x,ull C){
	if(taga[x])updd0(x,C*taga[x]);
	else val[x]+=C*sa[x],ta[x]+=C;
}
inline void upddb(int x,ull C){
	if(tagb[x])updd0(x,C*tagb[x]);
	else val[x]+=C*sb[x],tb[x]+=C;
}
inline void updd(int x,ull C){
	if(!taga[x]&&!tagb[x])val[x]+=C*sab[x],tab[x]+=C;
	else if(taga[x]&&!tagb[x])upddb(x,C*taga[x]);
	else if(!taga[x]&&tagb[x])updda(x,C*tagb[x]);
	else updd0(x,C*taga[x]*tagb[x]);
}
inline void pushdown(int x){
	if(tab[x])updd(ls(x),tab[x]),updd(rs(x),tab[x]),tab[x]=0;
	if(ta[x])updda(ls(x),ta[x]),updda(rs(x),ta[x]),ta[x]=0;
	if(tb[x])upddb(ls(x),tb[x]),upddb(rs(x),tb[x]),tb[x]=0;
	if(t[x])updd0(ls(x),t[x]),updd0(rs(x),t[x]),t[x]=0;
	if(taga[x])upda(ls(x),taga[x]),upda(rs(x),taga[x]),taga[x]=0;
	if(tagb[x])updb(ls(x),tagb[x]),updb(rs(x),tagb[x]),tagb[x]=0;
}
void Updatea(int L,int R,int C,int l,int r,int u){
	if(L<=l&&r<=R)return upda(u,C);
	int mid=(l+r)>>1;pushdown(u);
	if(L<=mid)Updatea(L,R,C,l,mid,ls(u));
	if(R>mid)Updatea(L,R,C,mid+1,r,rs(u));
	pushup(u);
}
void Updateb(int L,int R,int C,int l,int r,int u){
	if(L<=l&&r<=R)return updb(u,C);
	int mid=(l+r)>>1;pushdown(u);
	if(L<=mid)Updateb(L,R,C,l,mid,ls(u));
	if(R>mid)Updateb(L,R,C,mid+1,r,rs(u));
	pushup(u);
}
ull ask(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R)return val[u];
	int mid=(l+r)>>1;pushdown(u);
	return (L<=mid?ask(L,R,l,mid,ls(u)):0)+(R>mid?ask(L,R,mid+1,r,rs(u)):0);
}
ull ASK(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R)return sab[u];
	int mid=(l+r)>>1;pushdown(u);
	return (L<=mid?ASK(L,R,l,mid,ls(u)):0)+(R>mid?ASK(L,R,mid+1,r,rs(u)):0);
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int _,n;read(_),read(n);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<=n;++i)read(b[i]);
	int q;read(q);
	for(int i=1,l,r;i<=q;++i)read(l),read(r),vec[r].pb({l,i});
	build(1,n,1);
	for(int i=1;i<=n;++i){
		while(top1&&a[i]>a[st1[top1]])--top1;
		while(top2&&b[i]>b[st2[top2]])--top2;
		Updatea(st1[top1]+1,i,a[i],1,n,1),Updateb(st2[top2]+1,i,b[i],1,n,1),st1[++top1]=i,st2[++top2]=i;
		updd(1,1);for(auto it:vec[i])ans[it.id]=ask(it.l,i,1,n,1);
	}
	for(int i=1;i<=q;++i)printf("%llu\n",ans[i]);
	return 0;
}
