#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=3005;
int T,Q,n,a[N],b[N],s[N][N],mxa[N][N],mxb[N][N];
namespace Seg{
	int val[N*N<<2];
	inline void pushup(int x){
		val[x]=val[x*4]+val[x*4+1]+val[x*4+2]+val[x*4+3];
	}
	void bd(int x,int l1,int r1,int l2,int r2){
		if(l1==r1&&l2==r2)
			return val[x]=mxa[l1][l1]*mxb[l2][l2],void();
		int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
		bd(x*4,l1,mid1,l2,mid2);
		bd(x*4+1,l1,mid1,mid2+1,r2);
		bd(x*4+2,mid1+1,r1,l2,mid2);
		bd(x*4+3,mid1+1,r1,mid2+1,r2);
		pushup(x);
	}
	int ask(int x,int l1,int r1,int l2,int r2,int L1,int R1,int L2,int R2){
		if(l1>=L1&&r1<=R1&&l2>=L2&&r2<=R2)
			return val[x];
		int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1,res=0;
		if(L1<=mid1&&L2<=mid2) res+=ask(x*4,l1,mid1,l2,mid2,L1,R1,L2,R2);
		if(L1<=mid1&&R2>mid2) res+=ask(x*4+1,l1,mid1,mid2+1,r2,L1,R1,L2,R2);
		if(R1>mid1&&L2<=mid2) res+=ask(x*4+2,mid1+1,r1,l2,mid2,L1,R1,L2,R2);
		if(R1>mid1&&R2>mid2) res+=ask(x*4+3,mid1+1,r1,mid2+1,r2,L1,R1,L2,R2);
		return res;
	}
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mxa[i][i]=a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		mxb[i][i]=b[i];
	}
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++){
			mxa[i][j]=max(mxa[i][j-1],a[j]),mxb[i][j]=max(mxb[i][j-1],b[j]);
			s[i][j]+=mxa[i][j]*mxb[i][j];
		}
	for(int i=1;i<=n;i++)
		for(int j=n;j>=i;j--)
			s[i][j]+=s[i-1][j+1]-s[i-1][j]-s[i][j+1];
	cin>>Q;
	while(Q--){
		int l,r,ans=0;
		cin>>l>>r;
		for(int p=l;p<=r;p++)
			for(int q=p;q<=r;q++)
				ans+=mxa[p][q]*mxb[p][q];
		cout<<ans<<"\n";
	}
	return 0;
}
