#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e3+10;
struct ST{
	int f[N][30],Log[N];
	void init(int type);
	int query(int l,int r);
}st[2];
int n,a[N][2];
unsigned long long cnt[N][N];
int read(){
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
void ST::init(int type){
	Log[0]=-1;
	for(int i=1;i<=n;i++)
		f[i][0]=a[i][type],
		Log[i]=Log[i>>1]+1;
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int ST::query(int l,int r){
	int in=Log[r-l+1];
	return max(f[l][in],f[r-(1<<in)+1][in]);
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T=read();
	n=read();
	for(int i=1;i<=n;i++)a[i][0]=read();
	for(int i=1;i<=n;i++)a[i][1]=read();
	st[0].init(0),st[1].init(1);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			cnt[i][j]=st[0].query(i,j)*st[1].query(i,j);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cnt[i][j]=cnt[i][j]+cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
	T=read();
	while(T--){
		int l=read(),r=read();
//		int ans=0;
		unsigned long long ans=cnt[r][r]+cnt[l-1][l-1]-cnt[l-1][r]-cnt[r][l-1];
/*		for(int i=l;i<=r;i++)
			for(int j=i;j<=r;j++)
				ans+=cnt[i][j];*/
		cout<<ans<<endl;
	}
	return 0;
}