#include <bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
template <typename T>
bool read_(T &ready_get)
{
	T x=0,f=1;
	char ch=getchar();
	while(!('0'<=ch&&ch<='9'))
	{
		if(ch=='-') f=-1;
		if(ch==-1) return false;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	ready_get=f*x;
	return true;
}
int n;
ull s[3007][3007],a[250007],b[250007],sta[250007][21],stb[250007][21];
void init()
{
	for(int i=1;i<=n;++i)
		sta[i][0]=a[i],stb[i][0]=b[i];
	for(int j=1;j<=20;++j)
		for(int i=1;i+(1<<(j-1))-1<=n;++i)
		{
			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]);
		}
}
ull querya(int l,int r)
{
	int k=log2(r-l+1);
	return max(sta[l][k],sta[r-(1<<k)+1][k]);
}
ull queryb(int l,int r)
{
	int k=log2(r-l+1);
	return max(stb[l][k],stb[r-(1<<k)+1][k]);
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	read_(T),read_(n);
	for(int i=1;i<=n;++i)
		read_(a[i]);
	for(int i=1;i<=n;++i)
		read_(b[i]);
	init();
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
			s[i][j]=s[i][j-1]+querya(i,j)*queryb(i,j);
	int Q,l,r;
	read_(Q);
	while(Q--)
	{
		ull ans=0;
		read_(l),read_(r);
		for(int i=l;i<=r;++i)
			ans+=s[i][r];
		printf("%llu\n",ans);
	}
	return 0;
}