#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 300005
#define inf 0x3f3f3f3f
#define ull unsigned long long

int O,n,m,a[maxn],b[maxn];
ull res[maxn];

vector<pii>q[maxn];

int taga[maxn<<2],tagb[maxn<<2],len[maxn<<2];
ull s0[maxn<<2],s1[maxn<<2],s2[maxn<<2],s3[maxn<<2];
ull suma[maxn<<2],sumb[maxn<<2],sumab[maxn<<2],sum[maxn<<2];

void build(int p,int l,int r){
	len[p]=r-l+1;
	if(l==r)return;
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}

void up(int p){
	suma[p]=suma[p<<1]+suma[p<<1|1];
	sumb[p]=sumb[p<<1]+sumb[p<<1|1];
	sumab[p]=sumab[p<<1]+sumab[p<<1|1];
	sum[p]=sum[p<<1]+sum[p<<1|1];
}

void pt0(int p,ull t){
	s0[p]+=t;
	sum[p]+=sumab[p]*t;
}
void pt1(int p,ull t){
	s1[p]+=t;
	sum[p]+=suma[p]*t;
}
void pt2(int p,ull t){
	s2[p]+=t;
	sum[p]+=sumb[p]*t;
}
void pt3(int p,ull t){
	s3[p]+=t;
	sum[p]+=len[p]*t;
}

void ptA(int p,int t){
	taga[p]=t;
	suma[p]=1ull*t*len[p];
	if(tagb[p]!=-1) sumab[p]=1ull*t*len[p]*tagb[p];
	else sumab[p]=1ull*t*sumb[p];
}
void ptB(int p,int t){
	tagb[p]=t;
	sumb[p]=1ull*t*len[p];
	if(taga[p]!=-1) sumab[p]=1ull*t*len[p]*taga[p];
	else sumab[p]=1ull*t*suma[p];
}

void pt(int p,int ta,int tb,ull t0,ull t1,ull t2,ull t3){
	if(t0){
		if(taga[p]!=-1 && tagb[p]!=-1) pt3(p,t0*taga[p]*tagb[p]);
		else if(taga[p]!=-1) pt2(p,t0*taga[p]);
		else if(tagb[p]!=-1) pt1(p,t0*tagb[p]);
		else pt0(p,t0);
		
	}
	if(t1){
		if(taga[p]!=-1) pt3(p,t1*taga[p]);
		else pt1(p,t1);
	//	if(p==8)cout<<"Smp "<<t1<<" "<<tagb[p]<<" "<<sum[p]<<"\n";
	}
	if(t2){
		if(tagb[p]!=-1) pt3(p,t2*tagb[p]);
		else pt2(p,t2);
	}
	if(t3){
		pt3(p,t3);
	}
	if(ta!=-1) ptA(p,ta);
	if(tb!=-1) ptB(p,tb); 
}
void down(int p){
	pt(p<<1,  taga[p],tagb[p],s0[p],s1[p],s2[p],s3[p]);
	pt(p<<1|1,taga[p],tagb[p],s0[p],s1[p],s2[p],s3[p]);
	taga[p]=tagb[p]=-1;
	s0[p]=s1[p]=s2[p]=s3[p]=0;
//	assert(suma[p]==suma[p<<1]+suma[p<<1|1]);
//	assert(sumb[p]==sumb[p<<1]+sumb[p<<1|1]);
//	assert(sumab[p]==sumab[p<<1]+sumab[p<<1|1]);
//	assert(sum[p]==sum[p<<1]+sum[p<<1|1]);
}

void mdfA(int p,int l,int r,int nl,int nr,int v)
{
//	if(p==1)cout<<"mdfa "<<nl<<" "<<nr<<" "<<v<<"\n";
	if(l>=nl&&r<=nr){
		ptA(p,v);
		return;
	}
	int mid=l+r>>1; down(p);
	if(nl<=mid)mdfA(p<<1,l,mid,nl,nr,v);
	if(nr>mid)mdfA(p<<1|1,mid+1,r,nl,nr,v);
	up(p);
}

void mdfB(int p,int l,int r,int nl,int nr,int v)
{
//	if(p==1)cout<<"mdfb "<<nl<<' '<<nr<<" "<<v<<"\n";
	if(l>=nl&&r<=nr){
		ptB(p,v);
		return;
	}
	int mid=l+r>>1; down(p);
	if(nl<=mid)mdfB(p<<1,l,mid,nl,nr,v);
	if(nr>mid)mdfB(p<<1|1,mid+1,r,nl,nr,v);
	up(p);
}

ull ask(int p,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr)return sum[p];
	int mid=l+r>>1; down(p);
	ull res=0;
	if(ql<=mid)res+=ask(p<<1,l,mid,ql,qr);
	if(qr>mid)res+=ask(p<<1|1,mid+1,r,ql,qr);
	return res;
}

int st1[maxn],top1;
int st2[maxn],top2;

signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	O=read(),n=read();
	For(i,1,n)a[i]=read();
	For(i,1,n)b[i]=read();
	memset(taga,-1,sizeof taga);
	memset(tagb,-1,sizeof tagb);
	m=read();
	For(i,1,m){
		int l=read(),r=read();
		q[r].pb(mkp(l,i));
	}
	build(1,1,n);
	For(i,1,n){
		while(top1&&a[st1[top1]]<a[i])--top1;
		mdfA(1,1,n,st1[top1]+1,i,a[i]);
		st1[++top1]=i;
		while(top2&&b[st2[top2]]<b[i])--top2;
		mdfB(1,1,n,st2[top2]+1,i,b[i]);
		st2[++top2]=i;
		pt(1,-1,-1,1,0,0,0);
	//	cout<<len[1]<<" "<<suma[1]<<' '<<sumb[1]<<' '<<sumab[1]<<"\n";
	//	cout<<sum[1]<<"\n";
		for(auto t:q[i]){
			res[t.se]=ask(1,1,n,t.fi,i);
		}
	}
	For(i,1,m)cout<<res[i]<<'\n';
	return 0;
}
/*
0 5
4 1 2 5 3
2 4 3 5 1
0

*/
