#include<bits/stdc++.h>
using namespace std;

long long ans;
int Q,T,n;
int a[250005],b[250005],ta[250005],tb[250005];
int am[5000][5000],bm[5000][5000];

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];
	for(int i=1 ;i<=n ;i++){
		for(int j=n ;j>=1 ;j--){
			for(int k=i ;k<=j ;k++){
				am[i][j]=max(am[i][j],a[k]);
			}
		}
	}
	for(int i=1 ;i<=n ;i++) cin>>b[i];
	for(int i=1 ;i<=n ;i++){
		for(int j=n ;j>=1 ;j--){
			for(int k=i ;k<=j ;k++){
				bm[i][j]=max(bm[i][j],b[k]);
			}
		}
	}
	cin>>Q;
	while(Q--){
		ans=0;
		int l,r; cin>>l>>r;
		for(int i=l ;i<=r ;i++){
			for(int j=r ;j>=l ;j--){
				ans+=bm[i][j]*am[i][j];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
