#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define N 260000
struct node2{
	int l,id;
};
vector<node2> d[N];
int t,n,q,a[N],b[N],ans[N],la[N],lb[N];
struct node{
	int p,xy,x,y;
}tr[4*N];
struct node1{
	int cx,cy;
	int tagxy,tagx,tagy,tag1;
}tag[4*N];
void pushup(int p){
	tr[p]={tr[p*2].p+tr[p*2+1].p,tr[p*2].xy+tr[p*2+1].xy,tr[p*2].x+tr[p*2+1].x,tr[p*2].y+tr[p*2+1].y};
	return ;
}
void cnt(int p,int len,node1 now){
	auto &[cx,cy,tagxy,tagx,tagy,tag1]=tag[p];
	if(cx&&cy){
		tag1+=now.tagxy*cx*cy+now.tagx*cx*+now.tagy*cy+now.tag1;
	}
	else if(cx){
		tag1+=now.tagx*cx+now.tag1;
		tagy+=now.tagxy*cx+now.tagy;
	}
	else if(cy){
		tag1+=now.tagy*cy+now.tag1;
		tagx+=now.tagxy*cy+now.tagx;
	}
	else{
		tagxy+=now.tagxy;
		tagx+=now.tagx;
		tagy+=now.tagy;
		tag1+=now.tag1; 
	}
	if(now.cx){
		cx=now.cx;
	}
	if(now.cy){
		cy=now.cy;
	}
	auto &[s,xy,x,y]=tr[p];
	s+=now.tagxy*xy+now.tagx*x+now.tagy*y+now.tag1*len;
	if(now.cx&&now.cy){
		xy=now.cx*now.cy*len;
		x=now.cx*len;
		y=now.cy*len;
	}
	else if(now.cx){
		xy=now.cx*y;
		x=now.cx*len;
	}
	else if(now.cy){
		xy=now.cy*x;
		y=now.cy*len;
	}
	return ;
}
void pushdown(int p,int len1,int len2){
	if(tag[p].cx||tag[p].cy||tag[p].tagxy||tag[p].tagx||tag[p].tagy||tag[p].tag1){
		cnt(p*2,len1,tag[p]);
		cnt(p*2+1,len2,tag[p]);
		tag[p]={0,0,0,0,0,0};
	}
	return ;
}
void modify(int p,int l,int r,int nl,int nr,node1 now){
	if(nr<l||nl>r){
		return ;
	}
	if(l<=nl&&nr<=r){
		cnt(p,nr-nl+1,now);
		return ;
	}
	int mid=(nl+nr)/2;
	pushdown(p,mid-nl+1,nr-mid);
	modify(p*2,l,r,nl,mid,now);
	modify(p*2+1,l,r,mid+1,nr,now);
	pushup(p);
	return ; 
}
int query(int p,int l,int r,int nl,int nr){
	if(nr<l||nl>r){
		return 0;
	}
	if(l<=nl&&nr<=r){
		return tr[p].p;
	}
	int mid=(nl+nr)/2;
	pushdown(p,mid-nl+1,nr-mid);
	return query(p*2,l,r,nl,mid)+query(p*2+1,l,r,mid+1,nr);
}
signed main(){
	cin>>t>>n;
	a[0]=1e18;
	b[0]=1e18;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		la[i]=i;
		while(a[i]>=a[la[i]-1]+1){
			la[i]=la[la[i]-1];
		}
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		lb[i]=i;
		while(b[i]>=b[lb[i]-1]+1){
			lb[i]=lb[lb[i]-1];
		}
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		d[r].push_back((node2){l,i});
	}
	for(int i=1;i<=n;i++){
		modify(1,la[i],i,1,n,(node1){a[i],0,0,0,0,0});
		modify(1,lb[i],i,1,n,(node1){0,b[i],0,0,0,0});
		modify(1,1,i,1,n,(node1){0,0,1,0,0,0});
		for(auto x:d[i]){
			ans[x.id]=query(1,x.l,i,1,n);
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

只A了#10，其余全部WA/ll