#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long moo=184467440737095516;
int n,m,q;
long long a[250010],b[250010],fa[3010][3010],fb[3010][3010];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
	scanf("%d",&q);
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			long long oqp=0,opq=0;
			for(int k=i;k<=j;k++){
				oqp=max(oqp,a[k]);
				opq=max(opq,b[k]);
			}
			fa[i][j]=oqp;
			fb[i][j]=opq;
		}
	}
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		long long sum=0;
		for(int i=l;i<=r;i++){
			for(int j=i;j<=r;j++){
				sum=(sum+fa[i][j]*fb[i][j]%moo)%moo;
			}
		}
		printf("%lld\n",sum);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}