#include<bits/stdc++.h>
using namespace std;
#define ll __int128
template<typename T>inline void read(T &x){
	x=0;int f=1;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}
void put(ll x){
	if(x==0){putchar('0');return;}
	if(x<0){putchar('-');x=-x;}
	char ch[55];int tot;
	while(x){ch[++tot]=x%10+48;x/=10;}
	while(tot){putchar(ch[tot]),--tot;}
	return ;
}
const ll mod=(ll)1<<64;
int n,m,Size,block[200005];
int a[200005],b[200005];
ll ans[200005],ret;
struct node{
	int l,r,id;
	node(){
		l=r=id=0;
	}
	node(int x,int y,int z){
		l=x;r=y;id=z;
	}
	bool operator<(const node &y){
		return block[l]==block[y.l]?r<y.r:l<y.l;
	}
}e[200005];
int pa[200005],pb[200005];
int ba[200005],bb[200005];
int s1[200005],tp1,s2[200005],tp2;
inline void work(int x,int val,int l,int r,bool opt){
	int maxa=0,maxb=0,i,j,I,J;
	if(!opt){
		I=J=i=j=l;maxa=a[x],maxb=b[x];
		while(1){//l->r;
			if(!ba[i]){
				while(j){
					ret=((ret+1ll*val*maxa*maxb%mod*(bb[j]-J)%mod)%mod+mod)%mod;
					maxb=b[bb[j]];
					I=J=j=bb[j];
				}
				break;
			}
			if(!bb[j]){
				while(i){
					ret=((ret+1ll*val*maxa*maxb%mod*(ba[i]-I)%mod)%mod+mod)%mod;
					maxa=a[ba[i]];
					I=J=i=ba[i];
				}
				break;
			}
			if(ba[i]>bb[j]){
				ret=((ret+1ll*val*maxa*maxb%mod*(bb[j]-J)%mod)%mod+mod)%mod;
				maxb=b[bb[j]];
				I=J=j=bb[j];
			}else{
				ret=((ret+1ll*val*maxa*maxb%mod*(ba[i]-I)%mod)%mod+mod)%mod;
				maxa=a[ba[i]];
				I=J=i=ba[i];
			}
		}
	}else{
		I=J=i=j=r;maxa=a[x],maxb=b[x];
		while(1){//r->l;
			if(!pa[i]){
				while(j){
					ret=((ret+1ll*val*maxa*maxb%mod*(J-pb[j])%mod)%mod+mod)%mod;
					maxb=b[pb[j]];
					I=J=j=pb[j];
				}
				break;
			}
			if(!pb[j]){
				while(i){
					ret=((ret+1ll*val*maxa*maxb%mod*(I-pa[i])%mod)%mod+mod)%mod;
					maxa=a[pa[i]];
					I=J=i=pa[i];
				}
				break;
			}
			if(ba[i]>bb[j]){
				ret=((ret+1ll*val*maxa*maxb%mod*(J-pb[j])%mod)%mod+mod)%mod;
				maxb=b[pb[j]];
				I=J=j=pb[j];
			}else{
				ret=((ret+1ll*val*maxa*maxb%mod*(I-pa[i])%mod)%mod+mod)%mod;
				maxa=a[pa[i]];
				I=J=i=pa[i];
			}
		}
	}
	return;
}
signed main(){
//	return system("fc match.out match2.ans"),0;
//	freopen("match2.in","r",stdin);
//	freopen("match.out","w",stdout);
	read(n);read(n);Size=sqrt(n)+1;
	for(int i=1;i<=n;i++)read(a[i]),block[i]=i/Size;
	for(int i=1;i<=n;i++)read(b[i]);
	for(int i=n;i;i--){
		while(tp1&&a[s1[tp1]]<=a[i])--tp1;
		while(tp2&&b[s2[tp2]]<=b[i])--tp2;
		ba[i]=s1[tp1];
		bb[i]=s2[tp2];
		s1[++tp1]=i,s2[++tp2]=i;
	}tp1=tp2=0;
	for(int i=1;i<=n;i++){
		while(tp1&&a[s1[tp1]]<=a[i])--tp1;
		while(tp2&&b[s2[tp2]]<=b[i])--tp2;
		pa[i]=s1[tp1];
		pb[i]=s2[tp2];
		s1[++tp1]=i,s2[++tp2]=i;
	}
//	for(int i=1;i<=n;i++)printf("%d %d %d %d\n",ba[i],bb[i],pa[i],pb[i]);
	read(m);
	for(int i=1,l,r;i<=m;i++) read(l),read(r),e[i]=node(l,r,i);
	sort(e+1,e+1+m);
	for(int i=1,l=0,r=0;i<=m;i++){
		for(;r<e[i].r;++r) work(r+1,1,l,r+1,1);
		for(;l>e[i].l;--l) work(l-1,1,l-1,r,0);
		for(;r>e[i].r;--r) work(r,-1,l,r,1);
		for(;l<e[i].l;++l) work(l,-1,l,r,0);
		ans[e[i].id]=ret;
	}
	for(int i=1;i<=m;i++)put(ans[i]),putchar('\n');
	return 0;
}

