#include<bits/stdc++.h>
#define N 250005
using namespace std;
typedef unsigned long long ull;
int T,n;
int a[N],b[N];
inline int Rd()
{
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch)) f|=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
struct Seg
{
	int val[N<<2];
	void build(int p,int l,int r,bool flag)
	{
		if(l==r)
		{
			if(flag) val[p]=a[l];
			else val[p]=b[l];
			return ;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid,flag),build(p<<1|1,mid+1,r,flag);
		val[p]=max(val[p<<1],val[p<<1|1]);
	}
	int ask(int p,int l,int r,int L,int R)
	{
		if(L<=l&&R>=r) return val[p];
		int mid=l+r>>1,res=0;
		if(L<=mid) res=max(res,ask(p<<1,l,mid,L,R));
		if(R>mid) res=max(res,ask(p<<1|1,mid+1,r,L,R));
		return res;
	}
}t1,t2;
namespace pb
{
	const int M=3005;
	ull val[M][M],sum[M][M];
	void solve()
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<=n;j++)
			{
				int x=t1.ask(1,1,n,i,j),y=t2.ask(1,1,n,i,j);
				sum[i][j]=sum[i][j-1]+1llu*x*y;
			}
		}
		int Q;
		scanf("%d",&Q);
		while(Q--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			ull ans=0;
			for(int i=l;i<=r;i++) ans+=sum[i][r]-sum[i][l-1];
			printf("%llu\n",ans);
		}
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=Rd(),n=Rd();
	for(int i=1;i<=n;i++) a[i]=Rd();
	for(int i=1;i<=n;i++) b[i]=Rd();
	t1.build(1,1,n,1),t2.build(1,1,n,0); 
	pb::solve();
	return 0;
}