#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=3e5+10,M=3030;
#define ull unsigned long long
ull w[M][M];
int n,m,a[2][N],f[2][N][30];
struct query{int l,r,id;}q[N];
void build(int p)
{
	for(int i=1;i<=n;i++) f[p][i][0]=a[p][i];
	for(int j=1;j<=20;j++)
	    for(int i=1;i+(1<<j-1)<=n;i++)
	        f[p][i][j]=max(f[p][i][j-1],f[p][i+(1<<j-1)][j-1]);
}
int query(int p,int l,int r)
{
	int k=log2(r-l+1);return max(f[p][l][k],f[p][r-(1<<k)+1][k]);
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[0][i]);
	for(int i=1;i<=n;i++) scanf("%d",&a[1][i]);
	int Q;scanf("%d",&Q);build(0);build(1);
	if(n<=3000)
	{
		for(int l=1;l<=n;l++)
		{
			ull tmp=0;
			for(int r=l;r<=n;r++)
		    {
		    	tmp=1ull*query(0,l,r)*query(1,l,r);
		    	w[l][r]=w[l][r-1]+tmp;
			}
		}
	}
	while(Q--)
	{
		int l,r;scanf("%d%d",&l,&r);ull ans=0;
		if(n<=3000)
		{
			for(int t=l;t<=r;t++) ans+=w[t][r];
		}
		else
		{
			for(int x=l;x<=r;x++)
			    for(int y=x;y<=r;y++)
			        ans+=1ull*query(0,l,r)*query(1,l,r);
		}
		printf("%llu\n",ans);
	}
	return 0;
}