#include<bits/stdc++.h>
using namespace std;
#define N 250005
#define ull unsigned long long
int read(){
	int w=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-f:f),c=getchar();
	while(c>='0'&&c<='9')w=w*10+c-'0',c=getchar();
	return w*f;
}
int T,n,q,a[N],b[N];
namespace sub1{
	#define NN 3005
	ull w[NN][NN];
	bool is(){
		return n<=3000&&q<=3000;
	}
	void solve(){
		for(int i=1;i<=n;i++){
			int maxa=0,maxb=0;
			for(int j=i;j<=n;j++){
				maxa=max(maxa,a[j]),maxb=max(maxb,b[j]);
				w[i][j]=w[i][j-1]+1llu*maxa*maxb;
			}
		}
		while(q--){
			int l=read(),r=read();
			ull ans=0;
			for(int i=l;i<=r;i++)
				ans+=w[i][r];
			printf("%llu\n",ans);
		}
	}
	#undef NN
}
namespace sub2{
	#define M 18
	int nxta[N],nxtb[N],lg[N],maxn[M][N];
	bool is(){
		return n<=3000&&q<=3000;
	}
	int qry(int l,int r){
		int x=lg[r-l+1];
		return max(maxn[x][r],maxn[x][l+(1<<x)-1]);
	}
	void init(){
		lg[0]=-1;
		for(int i=1;i<N;i++)
			lg[i]=lg[i>>1]+1;
		for(int i=1;i<=n;i++)
			maxn[0][i]=a[i];
		for(int i=1;i<M;i++)
			for(int j=(1<<i);j<=n;j++)
				maxn[i][j]=max(maxn[i-1][j],maxn[i-1][j-(1<<(i-1))]);
		for(int i=1;i<=n;i++){
			int l=i+1,r=n,res=n+1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(qry(l,mid)>a[i])res=mid,r=mid-1;
				else l=mid+1;
			}
			nxta[i]=res;
		}
		for(int i=1;i<=n;i++)
			maxn[0][i]=b[i];
		for(int i=1;i<M;i++)
			for(int j=(1<<i);j<=n;j++)
				maxn[i][j]=max(maxn[i-1][j],maxn[i-1][j-(1<<(i-1))]);
		for(int i=1;i<=n;i++){
			int l=i+1,r=n,res=n+1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(qry(l,mid)>b[i])res=mid,r=mid-1;
				else l=mid+1;
			}
			nxtb[i]=res;
		}
	}
	void solve(){
		init();
		while(q--){
			int l=read(),r=read(),now,na,nb;
			ull ans=0;
			for(int i=l;i<=r;i++){
				now=i,na=a[i],nb=b[i];
				while(now<=r){
					int nxt=min(min(nxta[now],nxtb[now]),r+1);
					ans+=1llu*(nxt-now)*na*nb,now=nxt,na=max(na,a[nxt]),nb=max(nb,b[nxt]);
				}
			}
			printf("%llu\n",ans);
		}
	}
	#undef M
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read(),n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		b[i]=read();
	q=read();
	if(sub1::is())sub1::solve();
	else sub2::solve();
	return 0;
}