#include<bits/stdc++.h>
#define int unsigned long long
#define F(i,j,k) for(register int i=j,_End=k;i<=_End;i++)
#define D(i,j,k) for(register int i=j,_End=k;i>=_End;i--)
#define N 1000005
using namespace std;

inline void ri(int &x)
{
	x=0;
	char c=getchar();
	while(c<48||c>57)	c=getchar();
	while(c>47&&c<58)	x=x*10+c-48,c=getchar();
}

int T,n,q,l,r,a[N],b[N],sta[N][21],stb[N][21],ans[3005][3005],sum[3005][3005];

int querya(int l,int r)
{
	int k=log2(r-l+1);
	return max(sta[l][k],sta[r-(1<<k)+1][k]);
}

int queryb(int l,int r)
{
	int k=log2(r-l+1);
	return max(stb[l][k],stb[r-(1<<k)+1][k]);
}

signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ri(T),ri(n);
	F(i,1,n)	ri(a[i]),sta[i][0]=a[i];
	F(i,1,n)	ri(b[i]),stb[i][0]=b[i];
	F(j,1,20)
	{
		F(i,1,n)
		{
			if(i+(1<<j)-1<=n)
			{
				sta[i][j]=max(sta[i][j-1],sta[i+(1<<(j-1))][j-1]);
				stb[i][j]=max(stb[i][j-1],stb[i+(1<<(j-1))][j-1]);
			}
		}
	}
	F(i,1,n)
		F(j,i,n)
			ans[i][j]=querya(i,j)*queryb(i,j);
	F(i,1,n)
		F(j,i,n)
			sum[i][j]=sum[i][j-1]+ans[i][j];
	ri(q);
	while(q--)
	{
		ri(l),ri(r);
		int res=0;
		F(i,l,r)
//			F(j,i,r)
				res+=sum[i][r];
		printf("%llu\n",res);
	}
	return 0;
}
