#include<bits/stdc++.h>
#define ll long long
#define IN inline
#define rg register
#define re(i,a,b) for(rg int i=a,i##up=b;i<=i##up;i++)
#define er(i,a,b) for(rg int i=a,i##dw=b;i>=i##dw;i--)
#define go(i,x) for(rg int i=head[x];i;i=nxt[i])
#define mem(a,x) memset(a,x,sizeof a)
const int N=2.5e5+5;
IN ll read(){
	rg ll res=0,f=1; rg char c; do f&=((c=getchar())!='-'); while(c<'0' || '9'<c);
	for(;'0'<=c && c<='9';res=res*10+(c^48),c=getchar()); return f?res:-res;
}
IN void tomax(int &a,int b){a<b?a=b:0;}
int id,n,q,a[N],b[N];
namespace S1{
	ll ans;
	IN int amx(int l,int r){int mx=0; re(i,l,r) tomax(mx,a[i]); return mx;}
	IN int bmx(int l,int r){int mx=0; re(i,l,r) tomax(mx,b[i]); return mx;}
	void sol(){
		ans=0;
		re(i,1,q=read()){
			int L=read(),R=read();
			re(l,L,R) re(r,l,R) ans+=amx(l,r)*bmx(l,r);
			printf("%lld\n",ans);
		} 
	}
}
int main(){
	freopen("match.in","r",stdin),freopen("match.out","w",stdout);
	id=read(),n=read(); re(i,1,n) a[i]=read(); re(i,1,n) b[i]=read();
	if(id<=2) S1::sol();
	return 0;
}
