#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=3e3+7;
ull read(){
	char c;
	ull x=0;
	while(!isdigit(c=getchar()));
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x;
}
ull T,n,q,l,r,res,a[N],b[N],f[N][N],g[N][N];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();
	n=read();
	for(ull i=1;i<=n;++i)
		a[i]=read();
	for(ull i=1;i<=n;++i)
		b[i]=read();
	q=read();
	for(ull i=1;i<=n;++i){
		ull x=0,y=0;
		for(ull j=i;j;--j){
			x=max(x,a[j]);
			y=max(y,b[j]);
			g[i][j]=g[i][j+1]+x*y;
		}
	}
	for(ull i=1;i<=n;++i)
	for(ull j=i;j<=n;++j)
		f[i][j]=f[i][j-1]+g[j][i];
	while(q--){
		l=read();
		r=read();
		printf("%llu\n",f[l][r]);
	}
	return 0;
}