#include<bits/stdc++.h>
using namespace std;
#define Ul unsigned long long
Ul ma[300000],mb[300000],f[3010][3010],a[300000],b[300000],df[3010]; 
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int t;
	int n,m;
	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]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++)
		ma[j]=max(ma[j],a[i]),
		mb[j]=max(mb[j],b[i]),
		df[j]=df[j-1]+ma[j]*mb[j];	
		for(int j=1;j<=i;j++)
		f[j][i]=f[j][i-1]+df[i]-df[j-1];
	}
	scanf("%d",&m);
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%llu\n",f[l][r]);
	}
	return 0;
}