#include<bits/stdc++.h>
using namespace std;
int t,n,q;
int a[35],b[35];
int fa[35][35],fb[35][35];
long long ans;
int l,r;
int maxn(int c[],int j,int k) {
	int back_=0;
	for(int i=j; i<=k; i++) {
		back_=max(back_,c[i]);
	}
	return back_;
}
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>t>>n;
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int i=1; i<=n; i++)
		scanf("%d",&b[i]);
	cin>>q;
	for(int i=1; i<=q; i++) {
		ans=0;
		scanf("%d%d",&l,&r);
		int qa,qb;
		for(int j=l; j<=r; j++) {
			for(int z=l; z<=r; z++) {
				if(j>z)continue;
				if(!fa[j][z]) {
					qa=maxn(a,j,z);
					fa[j][z]=qa;
				}
				if(!fb[j][z]) {
					qb=maxn(b,j,z);
					fb[j][z]=qb;
				}
				ans=ans+fb[j][z]*fa[j][z];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
