#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 250010;
int T,n;
ll a[N],b[N];
ll fa[N][20],fb[N][20];
int q,l,r;
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("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
	}
	int k;
	for(int i=1;i<=n;i++){
		fa[i][0]=a[i];
		fb[i][0]=b[i];
		for(int j=1;(i+(1<<(j-1)))<=n;j++){
			fa[i][j]=fa[i][j-1];
			fb[i][j]=fb[i][j-1];
			if(j==1) k=i;
			else k=i+(1<<(j-2));
			for(k;k<=i+(1<<(j-1));k++){
				fa[i][j]=max(fa[i][j],a[k]);
				fb[i][j]=max(fb[i][j],b[k]);
			}
		}
	}
	scanf("%d",&q);
	ll x,y,ans,maxa,maxb;
	int j;
	while(q--){
		scanf("%d%d",&l,&r);
		ans=0;
		for(int s=l;s<=r;s++){
			for(int t=s;t<=r;t++){
				maxa=-1,maxb=-1;
				for(int i=s;i<=t;i++){
					j=0;
					while((i+(1<<j))<=t) j++;
					j--;
					if(j==-1){
						maxa=max(maxa,fa[i][0]);
						maxb=max(maxb,fb[i][0]);
					}else{
						maxa=max(maxa,fa[i][j]);
						maxb=max(maxb,fb[i][j]);
					}
				}
				ans+=maxa*maxb;
			}
		}
		printf("%lld\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}