/*let life be like summer flowers*/
/*by wind_seeker*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010,M=3e5+1e3,inf=1e18;

inline int read(){
	int res=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) res=(res<<3)+(res<<1)+(c^48);
	return res*f;
}

int T,n,Q,a[M],b[M],ansa[N][N],ansb[N][N],mod;

#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
struct TREE{
	int suma,sumb;
}t[N<<2];
void push_up(int rt){t[rt].suma=max(t[ls].suma,t[rs].suma);t[rt].sumb=max(t[ls].sumb,t[rs].sumb);}
void build(int rt,int l,int r){
	if(l==r) return t[rt].suma=a[l],t[rt].sumb=b[l],void();
	int mid=(l+r)>>1;
	build(lson),build(rson);
	push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr,int op){
	if(ql<=l&&r<=qr&&op==1) return t[rt].suma;
	if(ql<=l&&r<=qr&&op==2) return t[rt].sumb;
	int res=-inf,mid=(l+r)>>1;
	if(ql<=mid) res=max(res,query(lson,ql,qr,op));
	if(mid<qr) res=max(res,query(rson,ql,qr,op));
	return res;
}

int Qpower(int a,int b){
	int res=1;
	for(;b;a=a*a,b>>=1){
		if(b&1) res=res*a;
	}
	return res;
}

signed 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();
	build(1,1,n);
	if(T<=5){
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				ansa[i][j]=query(1,1,n,i,j,1),ansb[i][j]=query(1,1,n,i,j,2);
		Q=read();
		for(int i=1,l,r;i<=Q;i++){
			l=read(),r=read();
			int res=0;
			for(int j=l;j<=r;j++)
				for(int k=j;k<=r;k++)
					res=(res+ansa[j][k]*ansb[j][k]);
			printf("%lld\n",res);
		}	
	}
	else{
		Q=read();
		for(int i=1,l,r;i<=Q;i++){
			l=read(),r=read();
			int res=0;
			for(int j=l;j<=r;j++)
				for(int k=j;k<=r;k++)
					res=(res+query(1,1,n,j,k,1)*query(1,1,n,j,k,2));
			printf("%lld\n",res);
		}
	}
	return 0;
}

