#include<bits/stdc++.h>
using namespace std;
unsigned long long f[3010][3010],g[3010][3010];
unsigned long long a[3010],b[3010];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int idd,n;
	cin>>idd>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i];
	for(int l=1;l<=n;l++){
		unsigned long long s1=0,s2=0;
		for(int r=l;r<=n;r++){
			s1=max(s1,a[r]);
			s2=max(s2,b[r]);
			f[l][r]=s1*s2;
			g[l][r]=g[l][r-1]+f[l][r];
		}
	}
	int q;
	cin>>q;
	while(q--){
		unsigned long long ans=0;
		int a,b;
		cin>>a>>b;
		for(int i=a;i<=b;i++){
			ans+=g[i][b];
		}
		cout<<ans<<"\n";
	}
	return 0;
}