#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=250000;
const unsigned long long M=18446744073709551615;
int a[N],b[N],T,n;
int st1[N][50],st2[N][30];
void st(){
	for(int i=1;i<=n;i++) st1[i][0]=a[i];
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<(i-1))<=n;j++){
			st1[j][i]=max(st1[j][i-1],st1[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i=1;i<=n;i++) st2[i][0]=b[i];
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<(i-1))<=n;j++){
			st2[j][i]=max(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
		}
	}
}
int max(int a,int b){
	if(a>=b) return a;
	else return b;
}
int Q(int l,int r){
	int k=log2(r-l+1);
	return max(st1[l][k],st1[r-(1<<k)+1][k])*max(st2[l][k],st2[r-(1<<k)+1][k]);
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read(),n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	st();
	int qn=read();
	for(int t=1;t<=qn;t++){
		int l=read(),r=read();
		unsigned long long ans=0;
		for(int i=l;i<=r;i++)
			for(int j=i;j<=r;j++)
				ans+=Q(i,j)%M,ans%=M;
		printf("%lld\n",ans%M);
	}
	return 0;
}