#include<bits/stdc++.h>
#define N 250010
#define M 3010
#define ll unsigned long long
using namespace std;

int T,n,q,l,r;
int a[N],b[N],g1[M][M],g2[M][M];
ll f[M][M];

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("%d",&a[i]);
	for(int i = 1; i <= n; i++) scanf("%d",&b[i]);
	if(n<=3000) {
		for(int i = 1; i <= n; i++)
			g1[i][i]=a[i],g2[i][i]=b[i],f[i][i]=(ll)a[i]*b[i];
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j+i-1<=n; j++) {
				int l=j,r=j+i-1;
				g1[l][r]=max(g1[l][r-1],g1[l+1][r]);
				g2[l][r]=max(g2[l][r-1],g2[l+1][r]);
				f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1]+(ll)g1[l][r]*g2[l][r];
			}
		}
	}
	else {
		
	}
	scanf("%d",&q);
	while(q--) {
		scanf("%d%d",&l,&r);
		printf("%llu\n",f[l][r]);
	}
	return 0;
}