#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct node {
	int l,r;
	int maxx;
} ta[N],tb[N];
int n,q;
int a[N],b[N];
int ans;
void builda(int x,int l,int r) {
	ta[x].l=l;
	ta[x].r=r;
	if(l==r) {
		ta[x].maxx=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	builda(x<<1,l,mid);
	builda(x<<1|1,mid+1,r);
	ta[x].maxx=max(ta[x<<1].maxx,ta[x<<1|1].maxx);
}
void buildb(int x,int l,int r) {
	tb[x].l=l;
	tb[x].r=r;
	if(l==r) {
		tb[x].maxx=b[l];
		return ;
	}
	int mid=(l+r)>>1;
	buildb(x<<1,l,mid);
	buildb(x<<1|1,mid+1,r);
	tb[x].maxx=max(tb[x<<1].maxx,tb[x<<1|1].maxx);
}
int aska(int x,int l,int r) {
	if(ta[x].l>=l&&ta[x].r<=r)
		return ta[x].maxx;
	int mid=(ta[x].l+ta[x].r)>>1;
	if(r<=mid)
		return 	aska(x<<1,l,r);
	else if(l>mid)
		return 	aska(x<<1|1,l,r);
	else {
		return max(aska(x<<1,l,r),aska(x<<1|1,l,r));
	}
}
int askb(int x,int l,int r) {
	if(ta[x].l>=l&&ta[x].r<=r)
		return tb[x].maxx;
	int mid=(tb[x].l+tb[x].r)>>1;
	if(r<=mid)
		return 	askb(x<<1,l,r);
	else if(l>mid)
		return 	askb(x<<1|1,l,r);
	else {
		return max(askb(x<<1,l,r),askb(x<<1|1,l,r));
	}
}

void doo(int l,int r) {
	for(int i=l; i<=r; i++)
		for(int j=i; j<=r; j++) {
			int maxa=0,maxb=0;
			maxa=aska(1,i,j);
			maxb=askb(1,i,j);
			ans=(maxa*maxb+ans);
		}

}
signed main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	cin>>T>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	for(int i=1; i<=n; i++)
		cin>>b[i];
	builda(1,1,n);
	buildb(1,1,n);
	cin>>q;
	while(q--) {
		int l,r;
		cin>>l>>r;
		ans=0;
		doo(l,r);
		cout<<ans<<endl;
	}
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/

