#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll Ni=3e3+10;
const ll N=3e5+10;
ll ma1[Ni][Ni],ma2[Ni][Ni];
ll ans[Ni][Ni];
ll T,n,a[N],b[N],Q,lll,rrr;
inline ll read(){
	char c=getchar(); ll d=0,e=1;
	while (c<'0'||c>'9') {
		if (c=='-') e=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9') {
		d=(d<<3)+(d<<1)+c-'0';
		c=getchar();
	}
	return d*e;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read(); n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=n;++i) b[i]=read();
	for (int i=1;i<=n;++i){
		ma1[i][i]=a[i]; ma2[i][i]=b[i];
		for (int j=i+1;j<=n;++j){
			ma1[i][j]=max(a[j],ma1[i][j-1]);
			ma2[i][j]=max(b[j],ma2[i][j-1]);
		}
	}
	for (int l=1;l<=n;++l){
		ans[l][l]=ma1[l][l]*ma2[l][l];
		for (int r=l+1;r<=n;++r){
			ans[l][r]=ans[l][l];
			for (int k=r;k>=l;--k)
				ans[l][r]+=ma1[k][r]*ma2[k][r];
		}
	}
	Q=read();
	while (Q--){
		lll=read(); rrr=read();
		printf("%lld\n",ans[lll][rrr]);
	}
	return 0;
}
