#include <bits/stdc++.h>
#define F(i,f,t) for(int i=(f),_end=(t);i<=_end;i++)
#define D(i,f,t) for(int i=(f),_end=(t);i>=_end;i--)
#define int unsigned long long
using namespace std;

template<typename T>
void re(T&a) {
	char c;
	T f=1;a=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') f=-1;
	while(isdigit(c)) a=a*10+c-'0',c=getchar();
	a*=f;
}
template<typename T,typename ...Arg>
void re(T&a,Arg&...arg) {
	re(a),re(arg...);
}
const int N=4000,M=100000;
typedef int intn[N],intm[M];
int n,m,B;
intn a,b;
int mxa[N][N],mxb[N][N],sm[N][N];
signed main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	re(T,n),B=sqrt(n);
	F(i,1,n)re(a[i]);
	F(i,1,n)re(b[i]);
	F(i,1,n) {
		F(j,i,n) mxa[i][j]=max(mxa[i][j-1],a[j]),
				 mxb[i][j]=max(mxb[i][j-1],b[j]),
				 sm[i][j]=mxa[i][j]*mxb[i][j];
		
	}
	re(m);
	F(i,1,m) {
		int ll,rr,Ans=0;
		re(ll,rr);
		F(i,ll,rr) F(j,i,rr) {
			Ans+=sm[i][j];
		}
		printf("%lld\n",Ans);
	}
	return 0;
}
