#include<bits/stdc++.h>
using namespace std;using ull=unsigned long long;
const int N=3e3+10;
int T,n,m;ull a[N],b[N],f[N][N],g[N][N],h[N][N];
int main(){
	freopen("match.in","r",stdin);freopen("match.out","w",stdout);
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++)scanf("%llu",&a[i]);
	for(int i=1;i<=n;i++)scanf("%llu",&b[i]);
	for(int i=1;i<=n;i++){
		f[i][i]=a[i];
		for(int j=i+1;j<=n;j++){
			f[i][j]=max(f[i][j-1],a[j]);
		}
	}
	for(int i=1;i<=n;i++){
		g[i][i]=b[i];
		for(int j=i+1;j<=n;j++){
			g[i][j]=max(g[i][j-1],b[j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			h[i][j]=f[i][j]*g[i][j];
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=i+1;j<=n;j++){
			h[i][j]+=h[i+1][j]+h[i][j-1]-h[i+1][j-1];
		}
	}
	scanf("%d",&m);
	for(int l,r;m--;){
		scanf("%d%d",&l,&r);
		printf("%llu\n",h[l][r]);
	}
	return 0;
}
