#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int Read(){
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
int a[3005][20],b[3005][20];
int lg[3005];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	lg[0]=-1;
	int T=Read(),n=Read();
	for(int i=1;i<=n;i++){
		a[i][0]=Read();
		lg[i]=lg[i/2]+1;
	} 
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i<=n;i++)
			a[i][j]=max(a[i][j-1],a[i+(1<<j-1)][j-1]);
	for(int j=1;j<=n;j++) b[j][0]=Read();
	for(int j=1;j<=lg[n];j++)for(int i=1;i<=n;i++)
			b[i][j]=max(b[i][j-1],b[i+(1<<j-1)][j-1]);
	int Q=Read();
	while(Q--){
		int ans=0;
		int l=Read(),r=Read();
		for ( int p=l ; p <= r ; p++ ){
			for ( int q=p;q<=r;q++){
				int len=lg[q-p+1];
//				cout << p << ' ' << q << ' ' << max(a[l][len],a[r-(1<<len)+1][len]) << ' ' << max(b[l][len],b[r-(1<<len)+1][len]) << endl;
				ans+=max(a[p][len],a[q-(1<<len)+1][len])*max(b[p][len],b[q-(1<<len)+1][len]);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

