#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
	int x=0;bool f=0;
	char c=gc();
	for(;c<'0'||c>'9';c=gc()) f|=(c=='-');
	for(;c>47&&c<58;c=gc()) x=(x<<3)+(x<<1)+(c&15);
	return (f?(~x)+1:x);
}
#define N 3005
#define ull unsigned long long
int sa[N][20],sb[N][20];//st_table a,st_table b
int a[N],b[N],n,q,T;
void init(){
	for(int i=n;i>0;i--){
		sa[i][0]=a[i];
		sb[i][0]=b[i];
		for(int j=1;i+(1<<j)<=n+1;j++){
			sa[i][j]=max(sa[i][j-1],sa[i+(1<<j-1)][j-1]);
			sb[i][j]=max(sb[i][j-1],sb[i+(1<<j-1)][j-1]);
		}
	}
}
ull getmax(int l,int r,int type){
	int lo=log2(r-l+1);
	return (type==1?max(sa[l][lo],sa[r-(1<<lo)+1][lo]):
					max(sb[l][lo],sb[r-(1<<lo)+1][lo]));
}
ull fi(int l,int r){
	return getmax(l,r,1)*getmax(l,r,0);
}
ull f[N][N],g[N][N];
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	init();
	for(int i=1;i<=n;i++){
		g[i][i]=fi(i,i);
		for(int j=i+1;j<=n;j++) g[i][j]=g[i][j-1]+fi(i,j);
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) f[1][i]+=g[j][i];
	for(int i=2;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			f[i][j]=f[i-1][j]-g[i-1][j];
		}
	}
	int l,r;
	cin>>q;
	while(q--){
		cin>>l>>r;
		cout<<f[l][r]<<endl;
	}
	return 0;
}

