#include<bits/stdc++.h>
#define W while
#define RI int
#define Cn const
#define CI Cn int& 
#define I inline
using namespace std;
Cn int N=3010,LG=20;
int Tt,n,a[N],b[N],Qt,L[N],R[N],Ans[N];
unsigned long long A[N][N],B[N][N];
/*L[N],R[N],MX[N][LG];
I int Q(CI l,CI r){
	RI i,j;unsigned long long X=0;for(i=l;i<=r;i++) for(j=i;j<=r;j++) X+=Qm()
}
class SegTree{
	private:
		int T[N<<2];
		#define mid (l+r>>1)
		#define PT CI x=1,CI l=1,CI r=n
		#define LT x<<1,l,mid
		#define RT x<<1|1,mid+1,r
		#define PU(x) (T[x]=max(T[x<<1],T[x<<1|1]))
	public:
		I void B(PT){
			if(l==r) return void(T[x]=a[l]);
			B(LT),B(RT),PU(x);
		}
		I int Q(CI L,CI R,PT){
			if(L<=l&&r<=R) return T[x];
			RI X=0;return L<=mid&&(X=max(X,Q(L,R,LT))),R>mid&&(X=max(X,Q(L,R,RT))),X;
		}
}T;*/
I void Q(CI l,CI r){
	RI i,j;unsigned long long X=0;for(i=l;i<=r;i++) for(j=i;j<=r;j++) X+=A[i][j]*B[i][j];
	printf("%u\n",X);
}
int main(){
	freopen("match.in","r",stdin),freopen("match.out","w",stdout);
	scanf("%d%d",&Tt,&n);
	RI i,j,l,r;for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) scanf("%d",&b[i]);
	for(i=1;i<=n;i++) for(A[i][i]=a[i],j=i+1;j<=n;j++) A[i][j]=max(A[i][j-1],1ull*a[j]);
	for(i=1;i<=n;i++) for(B[i][i]=b[i],j=i+1;j<=n;j++) B[i][j]=max(B[i][j-1],1ull*b[j]);
//	for(i=1;i<=n;i++){
//		j=i;W(j+1<=n&&a[j+1]<a[i]) j++;R[i]=j;
//		j=i;W(j-1>=1&&a[j-1]<a[i]) j--;L[i]=j;
//	}
//	for(i=1;i<=n;i++){
//		j=i;W(j+1<=n&&b[j+1]<b[i]) j++;r=j;
//		j=i;W(j-1>=1&&b[j-1]<b[i]) j--;l=j;
//		l=max(l,)
//		for(j=l;j<=r;j++) Ans[j]
//	}
	scanf("%d",&Qt);W(Qt--) scanf("%d%d",&l,&r),Q(l,r);
}