#include<iostream>
using namespace std;
int T,n,Q,ll,rr,tmp;
int a[250001],b[250001];
int fa[9000][9000],fb[9000][9000];

/*
int findmaxa(int p,int q){
	int maxx=a[p];
	for(int i=p+1;i<=q;i++){
		maxx=max(maxx,a[i]);
	}
	return maxx;
}

int findmaxb(int p,int q){
	int maxx=b[p];
	for(int i=p+1;i<=q;i++){
		maxx=max(maxx,b[i]);
	}
	return maxx;
}*/

void match(int l,int r){
	long long value=0;
	for(int p=l;p<=r;p++){
		for(int q=p;q<=r;q++){
			value+=fa[p][q]*fb[p][q];
		}
	}
	cout<<value<<endl;
}

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		fa[i][i]=a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		fb[i][i]=b[i];
	}
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			fa[i][j]=max(fa[i][j-1],fa[j][j]);
			fb[i][j]=max(fb[i][j-1],fb[j][j]);
		}
	}
	cin>>Q;
	for(int i=1;i<=Q;i++){
		cin>>ll>>rr;
		match(ll,rr);
	}
	return 0;
}