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

ll read(){
	ll x=0;char ch=getchar();bool f=0;
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=1;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return f?-x:x;
}

int const N=250000+3;
ll const Mo=(1<<30);
int T,n,cnt,a[N],b[N];
struct node{
	int id,ans,l,r;
}q[N];

bool cmp(node A,node B){
	if (A.l==B.l) return A.r<B.r;
	else return A.l<B.l;
}

bool cmp1(node A,node B){
	return A.id<B.id;
}

int 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();
	int Q=read();
	for (int i=1;i<=Q;i++){
		int x=read();
		int y=read();
		q[i].id=i;
		q[i].l=x;
		q[i].r=y;
	}
	sort(q+1,q+Q+1,cmp);
	cnt=1;
	for (int L=1;L<=n;L++){
		int mA=0,mB=0;
		int tot=0;
		for (int R=L;R<=n;R++){
			mA=max(mA,a[R]);
			mB=max(mB,b[R]);
			tot=mA*mB%Mo;
			tot%=Mo;
			for (int k=1;k<=Q;k++){
				if (q[k].l>L) break;
				if (q[k].l<=L && q[k].r>=R) q[k].ans=(q[k].ans+mA*mB%Mo)%Mo;
			}
		}
	}
	sort(q+1,q+Q+1,cmp1);
	for (int i=1;i<=Q;i++) cout<<q[i].ans<<endl;
	return 0;
}