#include<bits/stdc++.h>
using namespace std;
const unsigned long long N=pow(2,64);
unsigned long long t,n,q;
unsigned long long a[250010],b[250010];
bool aa,bb;
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&t,&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)scanf("%d",b+i);
	for(int i=1;i<n;i++){
		if(a[i]>a[i+1])aa=1;
		if(b[i]>b[i+1])bb=1;
	}
	
	scanf("%d",&q);
	while(q--){
		unsigned long long ans=0;
		int l,r;
		scanf("%d%d",&l,&r);
		if(aa==0&&bb==0){
			for(int i=l;i<=r;i++){
				for(int j=i;j<=r;j++){
					ans+=a[j]*b[j]%N;ans%=N;
				}
			}
		}
		else {
			unsigned long long maxx1=0,maxx2=0;
			for(int i=l;i<=r;i++){
				for(int j=i;j<=r;j++){
					maxx1=0;maxx2=0;
					for(int k=i;k<=j;k++){
						maxx1=max(a[k],maxx1);
						maxx2=max(b[k],maxx2);
					}
					ans+=maxx1*maxx2%N;ans%=N;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}