#include <bits/stdc++.h>
using namespace std;

//#define lowbit(x) (x&-x)
//
//const int N=2.5e5+5;
//int s[N],L[N],R[N],n,a[N],top,b[N];
//
//struct op{
//	int l,p,x;
//	inline bool operator < (const op &nt) const {
//		return l<nt.l;	
//	}
//};
//
//void doit(){
//	vector<op> Q;
//	int p,q;
//	cin>>p>>q;
//	top=0;s[0]=0;
//	for(int i=p;i<=q;i++){
//		while(top&&a[s[top]]<a[i]) top--;
//		L[i]=s[top]+1;
//		s[++top]=i;	
//	}
//	top=0;s[0]=q+1;
//	for(int i=q;i>=p;i--){
//		while(top&&a[s[top]]<a[i]) top--;
//		R[i]=s[top]-1;
//		s[++top]=i;
//		Q.push_back({L[i],L[i],1});
//		Q.push_back({L[i],R[i]+1,-1});
//		Q.push_back({R[i]+1,L[i],-1});
//		Q.push_back({R[i]+1,L[i],1});
//	}
//	top=0;s[0]=0;
//	for(int i=p;i<=q;i++){
//		while(top&&b[s[top]]<b[i]) top--;
//		L[i]=s[top]+1;
//		s[++top]=i;	
//	}
//	top=0;s[0]=q+1;
//	for(int i=q;i>=p;i--){
//		while(top&&b[s[top]]<b[i]) top--;
//		R[i]=s[top]-1;
//		s[++top]=i;
//		Q.push_back({R[i],});
//	}
//	sort(Q.begin(),Q.end());
//	for(int i=1;i<=n;i++)
////	for(int i=1;i<=n;i++){
////		cout<<L[i]<<" "<<R[i]<<endl;	
////	}
//}

#define ull unsigned long long

const int N=5e3+5;
ull s[N][N];
int n,a[N],b[N];

void doit(){
	int l,r;
	cin>>l>>r;
	cout<<s[l][l]+s[r+1][r+1]-s[l][r+1]-s[r+1][l]<<endl;
}

signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T,t;
	cin>>T>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		int ma=0,mb=0;
		for(int j=i;j<=n;j++){
			ma=max(ma,a[j]);
			mb=max(mb,b[j]);
			s[i][j]=ma*mb;
		}
	}
	for(int i=n;i;i--) for(int j=n;j;j--) s[i][j]+=s[i][j+1];
	for(int i=n;i;i--) for(int j=n;j;j--) s[i][j]+=s[i+1][j];
	cin>>t;
	while(t--) doit();
}