#include<bits/stdc++.h>
using namespace std;
constexpr int N=250000;
typedef unsigned long long ull;
int n,a[N+10],b[N+10];
struct _{
	int x,val;
};
deque<_> q1,q2;
struct qry{
	int l,r,id;
	bool operator<(const qry &ob)const{
		return l>ob.l;
	}
}Q[N+10];
int qtop;
ull ans[N+10];
ull s[2][1<<19],ss[1<<19],sum[1<<19];
ull add[2][1<<19],addd[1<<19],tag[2][1<<19],tagg[1<<19];
inline void pushup(int c,int rt){
	--c;
	s[c][rt]=s[c][rt<<1]+s[c][rt<<1|1];
	ss[rt]=ss[rt<<1]+ss[rt<<1|1];
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void putadd(int tp,int rt,ull c,int len){
	--tp;
	s[tp][rt]+=c*len;
	addd[rt]-=c*add[tp^1][rt];
	tagg[rt]-=c*tag[tp^1][rt];
	add[tp][rt]+=c;
	sum[rt]+=c*s[tp^1][rt];
}
void puttag(int tp,int rt,ull c){
	--tp;
	tag[tp][rt]+=c;
	tagg[rt]+=c*add[tp^1][rt];
	ss[rt]+=c*s[tp^1][rt];
}
void putadd_(int rt,ull c0,ull c1,ull c,int len){
	putadd(0,rt,c0,len);
	putadd(1,rt,c1,len);
	addd[rt]+=c;
	ss[rt]+=c*len;
}
void puttag(int rt,ull c0,ull c1,ull c,int len){
	puttag(0,rt,c0);
	puttag(1,rt,c1);
	tagg[rt]+=c;
	sum[rt]+=c*len;
}
void pushdown(int rt,int ls,int rs){
	if(add[0][rt]||add[1][rt]||addd[rt]){
		putadd_(rt<<1,add[0][rt],add[1][rt],addd[rt],ls);
		putadd_(rt<<1|1,add[0][rt],add[1][rt],addd[rt],rs);
		add[0][rt]=add[1][rt]=addd[rt]=0;
	}
	if(tag[0][rt]||tag[1][rt]||tagg[rt]){
		puttag(rt<<1,tag[0][rt],tag[1][rt],tagg[rt],ls);
		puttag(rt<<1|1,tag[0][rt],tag[1][rt],tagg[rt],rs);
		tag[0][rt]=tag[1][rt]=tagg[rt]=0;
	}
}
void update(int tp,int L,int R,ull c,int tim,int l,int r,int rt){
	if(L<=l&&r<=R) return putadd(tp,rt,c,r-l+1),puttag(tp,rt,tim*c);
	int m=l+r>>1;
	pushdown(rt,m-l+1,r-m);
	if(m>=L) update(tp,L,R,c,tim,l,m,rt<<1);
	if(m<R) update(tp,L,R,c,tim,m+1,r,rt<<1|1);
	pushup(tp,rt);
}
ull query(int L,int R,int tim,int l,int r,int rt){
	if(L<=l&&r<=R) return sum[rt]-ss[rt]*tim;
	int m=l+r>>1;
	pushdown(rt,m-l+1,r-m);
	ull rv=0;
	if(m>=L) rv+=query(L,R,tim,l,m,rt<<1);
	if(m<R) rv+=query(L,R,tim,m+1,r,rt<<1|1);
	return rv;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T>>n;
	int i;
	for(i=1;i<=n;++i) cin>>a[i];
	for(i=1;i<=n;++i) cin>>b[i];
	int q;
	cin>>q;
	for(i=1;i<=q;++i){
		int l,r;
		cin>>l>>r;
		Q[++qtop]={l,r,i};
	}
	q1.push_back({n+1,n+1});
	q2.push_back({n+1,n+1});
	sort(Q+1,Q+1+qtop);
	int top=0;
	for(i=n;i>=1;--i){
		_ tmp;
		while(q1.back().val<a[i]){
			tmp=q1.back();
			q1.pop_back();
			update(1,tmp.x,q1.back().x-1,-tmp.val,i,1,n,1);
		}
		update(1,i,q1.back().x-1,a[i],i,1,n,1);
		q1.push_back({i,a[i]});
		while(q2.back().val<b[i]){
			tmp=q2.back();
			q2.pop_back();
			update(2,tmp.x,q2.back().x-1,-tmp.val,i,1,n,1);
		}
		update(2,i,q2.back().x-1,b[i],i,1,n,1);
		q2.push_back({i,b[i]});
		while(top<qtop){
			if(Q[top+1].l==i){
				++top;
				ans[Q[top].id]=query(Q[top].l,Q[top].r,i-1,1,n,1);
			}
			else break;
		}
	}
	for(i=1;i<=qtop;++i) cout<<ans[i]<<'\n';
	return 0;
}
