#include<bits/stdc++.h>
#define N 250005
#define int unsigned long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int T,n,Q;
int a[N],b[N];
int fa[3005][3005],fb[3005][3005],sum[3005][3005];
signed 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();
	Q=read();
	for(int i=1;i<=n;++i){
		for(int j=i;j<=n;++j){
			fa[i][j]=max(fa[i][j-1],a[j]);
			fb[i][j]=max(fb[i][j-1],b[j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=i;j<=n;++j){
			sum[i][j]=(sum[i][j-1]+fa[i][j]*fb[i][j]);
		}
	}
	while(Q--){
		int l=read(),r=read(),ans=0;
		for(int p=l;p<=r;++p)
			ans=(ans+sum[p][r]);
		printf("%llu\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}