#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef unsigned long long ull;
typedef pair<ull,int> pii;
int t,n,q,wa[N][33],wb[N][33],Log[N];
ull fa[N][33],fb[N][33],a[N],b[N];
void init(){
	for(int i=1;i<=Log[n];i++){
		for(int j=1;j<=n-(1<<i)+1;j++){
			if(fa[j][i-1]>fa[j+(1<<i-1)][i-1]){
				fa[j][i]=fa[j][i-1];wa[j][i]=wa[j][i-1];
			}
			else{
				fa[j][i]=fa[j+(1<<i-1)][i-1];wa[j][i]=wa[j+(1<<i-1)][i-1];
			}
			if(fb[j][i-1]>fb[j+(1<<i-1)][i-1]){
				fb[j][i]=fb[j][i-1];wb[j][i]=wb[j][i-1];
			}
			else{
				fb[j][i]=fb[j+(1<<i-1)][i-1];wb[j][i]=wb[j+(1<<i-1)][i-1];
			}
		}
	}
}
pii aska(int l,int r){
	int k=Log[r-l+1];
	ull ma;int w;
	if(fa[l][k]>fa[r-(1<<k)+1][k]){
		ma=fa[l][k],w=wa[l][k];
	}else ma=fa[r-(1<<k)+1][k],w=wa[r-(1<<k)+1][k];
	return {ma,w};
}
pii askb(int l,int r){
	int k=Log[r-l+1];
	ull ma;int w;
	if(fb[l][k]>fb[r-(1<<k)+1][k]){
		ma=fb[l][k],w=wb[l][k];
	}else ma=fb[r-(1<<k)+1][k],w=wb[r-(1<<k)+1][k];
	return {ma,w};
}
ull ask(int l,int r){
	ull res=0;
	for(int i=l;i<=r;i++){
		int j=r;
		while(j>=i){
			pii a=aska(i,j),b=askb(i,j);
			int k=max(a.second,b.second);
			res+=a.first*b.first*(j-k+1);
			j=k-1;
		}
	}
	return res;
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>t>>n;
	for(int i=1,x;i<=n;i++){
		Log[i]=log2(i);
		scanf("%d",&x);a[i]=x;wa[i][0]=i;fa[i][0]=a[i];
	}
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);b[i]=x;wb[i][0]=i;fb[i][0]=b[i];
	}init();
	cin>>q;
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		cout<<ask(l,r)<<endl;
	}
	return 0;
}