#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int T,n,Q,l,r,a[N],b[N],a1[N][N],b1[N][N],op[N][N];
main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>T>>n;
	for(int i=1; i<=n; i++)cin>>a[i],a1[i][i]=a[i];
	for(int i=1; i<=n; i++)cin>>b[i],b1[i][i]=b[i];
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			b1[i][j]=max(b1[i][j-1],b[j]);
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			a1[i][j]=max(a1[i][j-1],a[j]);
	cin>>Q;
	while(Q--) {
		int s=0;
		cin>>l>>r;
		if(op[l][r]){
			cout<<op[l][r]<<"\n";
			continue;
		}
		for(int i=l; i<=r; i++)
			for(int j=i; j<=r; j++)
				s+=a1[i][j]*b1[i][j];
				cout<<s<<"\n";
				op[l][r]=s;
	}
	return 0;
}
