#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll tr1[4000001],tr2[4000001],n,a[1000001],b[1000001],t,q,ans;
ll md=(1<<31);
void buildtr1(ll l=1,ll r=n,ll p=1){
	if(l==r){
		tr1[p]=a[l];
		return;
	}
	ll mid=(l+r)/2;
	buildtr1(l,mid,2*p);
	buildtr1(mid+1,r,2*p+1);
	tr1[p]=max(tr1[2*p],tr1[2*p+1]);
}
void buildtr2(ll l=1,ll r=n,ll p=1){
	if(l==r){
		tr2[p]=b[l];
		return;
	}
	ll mid=(l+r)/2;
	buildtr2(l,mid,2*p);
	buildtr2(mid+1,r,2*p+1);
	tr2[p]=max(tr2[2*p],tr2[2*p+1]);
}
ll query1(ll l,ll r,ll p=1,ll cl=1,ll cr=n){
	if(cl>r||cr<l){
		return 0;
	}
	else if(cl>=l&&cr<=r){
		return tr1[p];
	}
	ll mid=(cl+cr)/2;
	return max(query1(l,r,2*p,cl,mid),query1(l,r,2*p+1,mid+1,cr));
}
ll query2(ll l,ll r,ll p=1,ll cl=1,ll cr=n){
	if(cl>r||cr<l){
		return 0;
	}
	else if(cl>=l&&cr<=r){
		return tr2[p];
	}
	ll mid=(cl+cr)/2;
	return max(query2(l,r,2*p,cl,mid),query2(l,r,2*p+1,mid+1,cr));
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>t>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	buildtr1();
	buildtr2();
	cin>>q;
	while(q--){
		ll l,r;
		ans=0;
		cin>>l>>r;
		for(ll p=l;p<=r;p++){
			for(ll q=p;q<=r;q++){
				ans=(ans+(query1(p,q))*query2(p,q))%md;
			}
		}
		cout<<ans<<endl;
	}
}
