#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5e4+5;
int n,m,T;
int a[N],b[N];
struct node{
	int l,r,maxx;
}tr1[N<<2],tr2[N<<2];
void pushup(int u){
	tr1[u].maxx=max(tr1[u<<1].maxx,tr1[u<<1|1].maxx);
	tr2[u].maxx=max(tr2[u<<1].maxx,tr2[u<<1|1].maxx);
}
void bld(int u,int l,int r){
	if(l==r){
		tr1[u]={l,r,a[l]};
		tr2[u]={l,r,b[l]};
	}
	else{
		tr1[u]={l,r};
		tr2[u]={l,r};
		int mid=l+r>>1;
		bld(u<<1,l,mid);bld(u<<1|1,mid+1,r);
		pushup(u);
	}
}
int q1(int u,int l,int r){
	//if(tr1[u].r<l||tr1[u].l>r)return 0;
	if(tr1[u].l>=l&&tr1[u].r<=r){
		return tr1[u].maxx;
	}
	else{
		int ans=0;
		int mid=tr1[u].l+tr1[u].r>>1;
		if(mid>=l)ans=max(ans,q1(u<<1,l,r));
		if(mid<r)ans=max(ans,q1(u<<1|1,l,r));
		return ans;
	}
}
int q2(int u,int l,int r){
	//if(tr2[u].r<l||tr2[u].l>r)return 0;
	if(tr2[u].l>=l&&tr2[u].r<=r){
		return tr2[u].maxx;
	}
	else{
		int ans=0;
		int mid=tr2[u].l+tr2[u].r>>1;
		if(mid>=l)ans=max(ans,q2(u<<1,l,r));
		if(mid<r)ans=max(ans,q2(u<<1|1,l,r));
		return ans;
	}
}

unsigned long long ans=0;
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0),cout.tie(0);
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int j=1;j<=n;j++){
		cin>>b[j];
	}
	int m;cin>>m;
	if(m<=30&&n<=30){
		while(m--){
			int l,r;
			cin>>l>>r;
			for(int p=l;p<=r;p++){
				for(int q=p;q<=r;q++){
					int maxa=0,maxb=0;
					for(int i=p;i<=q;i++){
						maxa=max(maxa,a[i]);
						maxb=max(maxb,b[i]);
					}
					ans+=maxa*maxb;
				}
			}
			cout<<ans<<'\n';
			ans=0;
		}
	}
	else{
		bld(1,1,n);
		while(m--){
			int l,r;
			cin>>l>>r;
			for(int p=l;p<=r;p++){
				for(int q=p;q<=r;q++){
					int maxa=q1(1,p,q),maxb=q2(1,p,q);
					//cout<<maxa<<" "<<maxb<<'\n';
					ans+=maxa*maxb;
				}
			}
			cout<<ans<<'\n';
			ans=0;
		}
	}
	return 0;
}