#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3030,M=3030;
ll a[N],b[N];
ll am[N][N],bm[N][N];
int T,n,m,q;
ll sol(int l,int r){
	ll sum=1,ans=0;
	for(int i=l;i<=r;i++){
		for(int j=i;j<=r;j++){
			sum=am[i][j]*bm[i][j];
			ans+=sum;
		}
	}
	return ans;
}
void init(){
	for(int i=1;i<=n;i++){
		ll maxn=a[i];
		for(int j=i;j<=n;j++){
			maxn=max(maxn,a[j]);
			am[i][j]=maxn;
		}
	}
	for(int i=1;i<=n;i++){
		ll maxn=b[i];
		for(int j=i;j<=n;j++){
			maxn=max(maxn,b[j]);
			bm[i][j]=maxn;
		}
	}
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	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]);
	}
	init();
	scanf("%d",&q);
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%lld\n",sol(l,r));
	}
	return 0;
}
