#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int d=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){d=(d<<3)+(d<<1)+c-'0';c=getchar();}
	return d;
}
const int N=3e5+5;
typedef unsigned long long ull;
int n;
int a[N],b[N],l[N],r[N];
int lg[N],sta[N][20],stb[N][20];
ull f[3005][3005];
ull ans;
void deal(int st[N][20]){
	for(int j=1;j<20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
}
ull check(int l,int r,int st[N][20]){
	int k=lg[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(false);
	cout.tie(0);
	int t=read();
	n=read();
	lg[0]=-1;
	for(int i=1;i<=n;i++){
		lg[i]=lg[i/2]+1;
		sta[i][0]=read();
	}
	for(int i=1;i<=n;i++)
		stb[i][0]=read();
	deal(sta);
	deal(stb);
	for(int k=0;k<=n;k++){
		for(int l=1;l+k<=n;l++){
			f[l][l+k]=f[l][l+k-1]+f[l+1][l+k]-f[l+1][l+k-1]+check(l,l+k,sta)*check(l,l+k,stb);
		}
	}
	int q=read();
	for(int i=1;i<=q;i++){
		ans=0;
		l[i]=read(),r[i]=read();
		cout<<f[l[i]][r[i]]<<endl;
	}
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/
