#include<bits/stdc++.h>
#define nm 500005
using namespace std;
void read( long long &n){
	char ch=getchar();
	unsigned long long k=0,f=1;
	while(ch<'0' or ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9'){
		k=k*10+ch-'0';
		ch=getchar();
	}
	n=f*k;
};
 long long a[nm],b,c[nm],d,e,f,g,h,T,l,r,lx[nm][25],bj[nm][25];
 long long ans;
 long long getans1(int l,int r){
	int w=log2(l+r);
	return max(lx[l][w],lx[r-(1<<w)+1][w]);
}
 long long getans2(int l,int r){
	int w=log2(l+r);
	return max(bj[l][w],bj[r-(1<<w)+1][w]);
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(T);
	read(b);
	for(int i=1;i<=b;i++){
		read(a[i]);
		lx[i][0]=a[i];
	}
	for(int i=1;i<=b;i++){
		read(c[i]);
		bj[i][0]=c[i];
	}
	for(int i=1;i<=19;i++){
		for(int j=1;j<=(b+1-(1<<i));j++){
			lx[j][i]=max(lx[j][i-1],lx[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i=1;i<=19;i++){
		for(int j=1;j<=(b-(1<<i)+1);j++){
			bj[j][i]=max(bj[j][i-1],bj[j+(1<<(i-1))][i-1]);
		}
	}
	read(T);
	while(T--){
		ans=0;
		read(l);
		read(r);
		for(int i=l;i<=r;i++){
			for(int j=i;j<=r;j++){
				ans=ans+getans1(i,j)*getans2(i,j);
			}
		}
		printf("%lld",ans);
		putchar('\n');
	}
}
//0 2
//2 1
//1 2
//1
//1 2