#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
long long read() {
	int f = 1;
	long long sum = 0;
	char c = getchar();
	while(!((c >= '0'&&c <= '9')||c == '-')) c = getchar();
	if(c == '-') f = -1,c = getchar();
	while(c >= '0'&&c <= '9') {
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}
long long n,maxa,maxb;
int a[250010],b[250010];
struct node{
	int l,r;
	long long ma,mb;
}tree[250000];
void build(int p,int l,int r){
	tree[p].l = l,tree[p].r = r;
	if(l == r) {
		tree[p].ma = a[l];
		tree[p].mb = b[l];
		return ;
	}
	int mid = (l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].ma = max(tree[p*2].ma,tree[p*2+1].ma);
	tree[p].mb = max(tree[p*2].mb,tree[p*2+1].mb);
	return;
}
void find(int x,int p,int q){
	if(p <= tree[x].l&&tree[x].r <= q) {
		maxa = max(maxa,tree[x].ma);
		maxb = max(maxb,tree[x].mb);
		return;
	}
	int mid = (tree[x].l + tree[x].r) /2;
	if(p <= mid) find(x*2,p,q);
	if(q >= mid+1) find(x*2+1,p,q);
	return;
}
const long long P = 9223372036854775808;
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	long long T = read();
	n = read();
	for(int i = 1;i <= n;i++){
		a[i] = read();
	}
	
	for(int i = 1;i <= n;i++){
		b[i] = read();
	}
	build(1,1,n);
	
	long long q = read();
	while(q--){
	    unsigned long long ans = 0;
		long long l = read(),r = read();
		for(int i = l;i <= r;i++){
			for(int j = i;j <= r;j++){
				maxa = maxb = -1e9;
				find(1,i,j);
				ans = (ans + maxa * maxb % P) %P;
			}
		}
		printf("%lld\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}