#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll = long long;
using ull = unsigned long long;
using namespace std;
int read(){
	char c=getchar();int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return f==1?x:~x+1;
}
int T,n;
int a[300010],b[300010];
int st1[300010][19],st2[300010][19];
int pos1[300010][19],pos2[300010][19];
int logt[300010];

struct ope{
	int x,l,r;
};
vector<ope>oper[300010];
void builda(int l,int r){
	if(l>r) return ;
	if(l==r){
		oper[l].pb(ope{a[l],l,l});
		return ;
	}
	int k=logt[r-l+1];
	int mid=(st1[l][k]>st1[r-(1<<k)+1][k]?pos1[l][k]:pos1[r-(1<<k)+1][k]);
	for(int i=l;i<=mid;++i){
		oper[i].pb(ope{a[mid],mid,r});
	}
//	oper[l].pb(ope{1,a[mid],mid,r});
//	oper[mid+1].pb(ope{2,a[mid],mid,r});
	builda(l,mid-1);builda(mid+1,r);
}
void buildb(int l,int r){
	if(l>r) return ;
	if(l==r){
		oper[l].pb(ope{b[l],l,l});
		return ;
	}
	int k=logt[r-l+1];
	int mid=(st2[l][k]>st2[r-(1<<k)+1][k]?pos2[l][k]:pos2[r-(1<<k)+1][k]);
	for(int i=l;i<=mid;++i){
		oper[i].pb(ope{b[mid],mid,r});
	}
//	oper[l].pb(ope{1,b[mid],mid,r});
//	oper[mid+1].pb(ope{2,b[mid],mid,r});
	buildb(l,mid-1);buildb(mid+1,r);
}
ull ans[300010];
struct que{
	int l,r,id;
};
vector<que>qry[300010];
ull sum[1200010],tag[12000010];
void pushup(int p){
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
void pushtag(int p,int x){
	sum[p]*=x;tag[p]*=x;
}
void pushdown(int p){
	if(tag[p]!=1){
		pushtag(p<<1,tag[p]);pushtag(p<<1|1,tag[p]);
		tag[p]=1;
	}
}
void clear(int p,int l,int r){
	if(sum[p]==r-l+1&&tag[p]==1) return ;
	sum[p]=r-l+1;tag[p]=1;
	if(l==r) return ;
	int mid=l+r>>1;
	clear(p<<1,l,mid);clear(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int L,int R,int x){
	if(l>=L&&r<=R){
		pushtag(p,x);
		return ;
	}
	int mid=l+r>>1;pushdown(p);
	if(L<=mid) update(p<<1,l,mid,L,R,x);
	if(R>mid) update(p<<1|1,mid+1,r,L,R,x);
	pushup(p);
}
ull query(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R) return sum[p];
	pushdown(p);
	int mid=l+r>>1;
	ull ret=0;
	if(L<=mid) ret+=query(p<<1,l,mid,L,R);
	if(R>mid) ret+=query(p<<1|1,mid+1,r,L,R);
	return ret;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();
	n=read();
	for(int i=2;i<=n;++i) logt[i]=logt[i>>1]+1;
	for(int i=1;i<=n;++i) a[i]=read(),st1[i][0]=a[i],pos1[i][0]=i;
	for(int i=1;i<=n;++i) b[i]=read(),st2[i][0]=b[i],pos2[i][0]=i;
	for(int j=1;j<=18;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			if(st1[i][j-1]>st1[i+(1<<j-1)][j-1]){
				st1[i][j]=st1[i][j-1];pos1[i][j]=pos1[i][j-1];
			}
			else{
				st1[i][j]=st1[i+(1<<j-1)][j-1];pos1[i][j]=pos1[i+(1<<j-1)][j-1];
			}
			if(st2[i][j-1]>st2[i+(1<<j-1)][j-1]){
				st2[i][j]=st2[i][j-1];pos2[i][j]=pos2[i][j-1];
			}
			else{
				st2[i][j]=st2[i+(1<<j-1)][j-1];pos2[i][j]=pos2[i+(1<<j-1)][j-1];
			}
		}
	}
	builda(1,n);
	buildb(1,n);
	int Q=read();
	for(int i=1;i<=Q;++i){
		int l=read(),r=read();
		for(int j=l;j<=r;++j){
			qry[j].pb(que{j,r,i});
		}
	}
	for(int i=1;i<=n;++i){
		clear(1,1,n);
		for(auto j:oper[i]){
			update(1,1,n,j.l,j.r,j.x);
		}
		for(auto j:qry[i]){
			ans[j.id]+=query(1,1,n,j.l,j.r);
		}
	}
	for(int i=1;i<=Q;++i) printf("%llu\n",ans[i]);
}