#include<bits/stdc++.h>
using namespace std;


const int N=250005;
const unsigned long long inf=18446744073709551615;

//struct node{
//	int l,r;
//	int ls,rs;
//	int maxn;
//	
//};
int a[N],b[N];
//int qa[N],heada=1,taila=0;
//int qb[N],headb=1,tailb=0;
int main(){
	freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
	int T,n;
	cin>>T>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	
	int Q;
	cin>>Q;
	while(Q--){
		int maxa=-1;
		int maxb=-1;
		unsigned long long ans=0;
//		memset(q,0,sizeof(q));
		int L,R;
		cin>>L>>R;
		for(int i=L;i<=R;i++){
			maxa=-1;
			maxb=-1;
			for(int j=i;j<=R;j++){
				maxa=max(maxa,a[j]);
				maxb=max(maxb,b[j]);
				ans+=maxa*maxb;
				if(ans!=inf)ans%=inf;
			}
		}
		cout<<ans<<endl;
	}
	//cout<<inf<<endl;
}
