#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') { if(c=='-') f=-1;c=getchar(); }
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
	return x*f;
}
void write(ull x){
	if(!x) return puts("0"),void();
	int q[50],t=0;
	while(x) q[++t]=x%10,x/=10;
	while(t) putchar(q[t--]^'0');
	puts("");
}
const int N=5e5+5;
int n,q;
int a[N],b[N];
int st1[N],top1;
int st2[N],top2;
int mx1[5005][5005],mx2[5005][5005];
signed main(){
	fre(match);
	int T=read();
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++){
		mx1[i][i]=a[i];
		mx2[i][i]=b[i];
		for(int j=i+1;j<=n;j++){
			mx1[i][j]=max(mx1[i][j-1],a[j]);
			mx2[i][j]=max(mx2[i][j-1],b[j]);
		}
	}
	q=read();
	while(q--){
		int l=read(),r=read();
		ull ans=0;
		for(int i=l;i<=r;i++)
			for(int j=i;j<=r;j++)
				ans+=1ll*mx1[i][j]*mx2[i][j];
		write(ans);
	}
	return 0;
}
/*
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') { if(c=='-') f=-1;c=getchar(); }
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
	return x*f;
}
void write(ull x){
	if(!x) return puts("0"),void();
	int q[50],t=0;
	while(x) q[++t]=x%10,x/=10;
	while(t) putchar(q[t--]^'0');
	puts("");
}
const int N=2.5e5+5;
int n,q;
ll a[N],b[N];
int st1[N],top1;
int st2[N],top2;
struct node{
	ll sa,sb;
	ull s;
};
node operator+(const node x,const node y){
	node res;
	res=x;
	res.sa+=y.sa;
	res.sb+=y.sb;
	res.s+=y.s;
	return res;
}
struct Tree{
	#define pl p<<1
	#define pr p<<1|1
	node dat[N<<2];
	int tag1[N<<2];
	int tag2[N<<2];
	int len[N<<2];
	void build(int p,int l,int r){
		len[p]=r-l+1;
		dat[p].sa=dat[p].sb=dat[p].s=tag1[p]=tag2[p]=0;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(pl,l,mid);
		build(pr,mid+1,r);
	}
	void cover1(int p,int v){
		tag1[p]+=v;
		dat[p].sa+=1ll*v*len[p];
		dat[p].s+=1ll*v*dat[p].sb;
	}
	void cover2(int p,int v){
		tag2[p]+=v;
		dat[p].sb+=1ll*v*len[p];
		dat[p].s+=1ll*v*dat[p].sa;
	}
	void down(int p){
		if(tag1[p]){
			cover1(pl,tag1[p]);
			cover1(pr,tag1[p]);
		}
		if(tag2[p]){
			cover2(pl,tag2[p]);
			cover2(pr,tag2[p]);
		}
		tag1[p]=tag2[p]=0;
	}
	void change1(int p,int l,int r,int L,int R,int v){
		if(l>=L&&r<=R) return cover1(p,v);
		down(p);
		int mid=(l+r)>>1;
		if(L<=mid) change1(pl,l,mid,L,R,v);
		if(R>mid) change1(pr,mid+1,r,L,R,v);
		dat[p]=dat[pl]+dat[pr];
	}
	void change2(int p,int l,int r,int L,int R,int v){
		if(l>=L&&r<=R) return cover2(p,v);
		down(p);
		int mid=(l+r)>>1;
		if(L<=mid) change2(pl,l,mid,L,R,v);
		if(R>mid) change2(pr,mid+1,r,L,R,v);
		dat[p]=dat[pl]+dat[pr];
	}
	node query(int p,int l,int r,int L,int R){
		if(l>=L&&r<=R) return dat[p];
		down(p);
		int mid=(l+r)>>1;
		if(R<=mid) return query(pl,l,mid,L,R);
		if(L>mid) return query(pr,mid+1,r,L,R);
		return query(pl,l,mid,L,R)+query(pr,mid+1,r,L,R);
	}
}T;
signed main(){
	fre(match2);
	int idT=read();
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	q=read();
	while(q--){
		int l=read(),r=read();
		int va=a[l-1];
		int vb=b[l-1];
		ull ans=0;
		T.build(1,1,n);
		top1=1,st1[top1]=l-1,a[l-1]=n+1;
		top2=1,st2[top2]=l-1,b[l-1]=n+1;
		
		
		T.change1(1,1,n,l,l,a[l]);
		T.change2(1,1,n,l,l,b[l]);
		st1[++top1]=l;
		st2[++top2]=l;
		
		ans=a[l]*b[l];
		
		for(int i=l+1;i<=r;i++){
			while(top1&&a[i]>a[st1[top1]]) T.change1(1,1,n,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]),top1--;
			while(top2&&b[i]>b[st2[top2]]) T.change2(1,1,n,st2[top2-1]+1,st2[top2],b[i]-b[st2[top2]]),top2--;
			st1[++top1]=i;
			st2[++top2]=i;
			T.change1(1,l,r,i,i,a[i]);
			T.change2(1,l,r,i,i,b[i]);
			ans+=T.query(1,1,n,l,i).s;
		}
		write(ans);
		a[l-1]=va;
		b[l-1]=vb;
	}
	return 0;
}
*/
