#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long 
#define maxn 100005
int T,n;
int a[maxn],b[maxn];
int la[maxn],ra[maxn];
int lb[maxn],rb[maxn];
int q;
int prea[3005][3005],preb[3005][3005];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%lld%lld",&T,&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
	}
	for(int i=1;i<=n;i++){
		prea[i][i]=a[i];
		preb[i][i]=b[i];
		for(int j=i+1;j<=n;j++){
			prea[i][j]=max(prea[i][j-1],a[j]);
			preb[i][j]=max(preb[i][j-1],b[j]);
		}
	}
	scanf("%lld",&q);
	while(q--){
		int l,r;
		scanf("%lld%lld",&l,&r);
		int ans=0;
		for(int p=l;p<=r;p++){
			for(int q=p;q<=r;q++){
				ans+=prea[p][q]*preb[p][q];
			}
		}
		printf("%lld\n",ans);
	}	
}