#include<bits/stdc++.h>
using namespace std;
#define maxn int(1e5+7)
#define ll unsigned long long
ll mi[35];
ll n;
ll a[maxn],ma[maxn][35],b[maxn],mb[maxn][35];
inline ll read(){
	ll num=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		num=num*10+c-48;
		c=getchar();
	}
	return num;
}
void init(){
	mi[0]=1;
	for(int i=1;i<=26;i++){
		mi[i]=mi[i-1]<<1;
	}
	for(int i=1;i<=n;i++){
		ma[i][0]=a[i];
		mb[i][0]=b[i];
	}
	for(int i=1;i<=26;i++){
		for(int j=1;j+mi[i]-1<=n;j++){
			ma[j][i]=max(ma[j][i-1],ma[min(n,j+mi[i]-mi[i-1])][i-1]);
			mb[j][i]=max(mb[j][i-1],mb[min(n,j+mi[i]-mi[i-1])][i-1]);
		}
	}
}
ll query(int l,int r){
	for(int i=1;i<=26;i++){
		if(r-l+1>=mi[i-1]&&r-l+1<mi[i]){
			return (max(ma[l][i-1],ma[r-mi[i-1]+1][i-1])*max(mb[l][i-1],mb[r-mi[i-1]+1][i-1]));
		}
	}
	return 0;
}
ll answer(int l,int r){
	ll ans=0;
	for(int i=l;i<=r;i++){
		for(int j=i;j<=r;j++){
			ans+=query(i,j);
		}
	}
	return ans;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		b[i]=read();
	}
	init();
	int q;
	cin>>q;
	for(;q;--q){
		int l=read();
		int r=read();
		printf("%lld\n",answer(l,r));
	}
	return 0;
}
