//AFOÁË£¬¿ª°Ú£¡ 
#include<bits/stdc++.h>
#define Cn const
#define CI Cn int&
#define N 250000
#define ull unsigned long long
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[30],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	void read(int& x) {x=0;while(!isdigit(oc=tc()));while(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	void writeln(ull x) {while(OS[++OT]=x%10+48,x/=10);while(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int n,Qt,a[N+5],b[N+5];
namespace BF
{
	#define BN 3000
	ull f[BN+5][BN+5];void Solve()
	{
		int i,j,A,B;for(i=n;i;--i) for(A=B=0,j=i;j<=n;++j)
		A=max(A,a[j]),B=max(B,b[j]),f[i][j]=f[i][j-1]+f[i+1][j]-f[i+1][j-1]+1ull*A*B;
		int l,r;while(Qt--) read(l),read(r),writeln(f[l][r]);
	}
}
namespace DC
{
	int A[N+5],B[N+5];ull ans,SA[N+5],SB[N+5],S[N+5];void Solve(int l,int r)
	{
		if(l==r) return (void)(ans+=a[l]*b[l]);int i,u=l+r>>1;Solve(l,u),Solve(u+1,r);
		for(A[u]=a[u],B[u]=b[u],i=u-1;i>=l;--i) A[i]=max(A[i+1],a[i]),B[i]=max(B[i+1],b[i]);
		for(A[u+1]=a[u+1],B[u+1]=b[u+1],i=u+2;i<=r;++i) A[i]=max(A[i-1],a[i]),B[i]=max(B[i-1],b[i]);
		for(SA[u]=SB[u]=S[u]=0,i=u+1;i<=r;++i) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],S[i]=S[i-1]+1ull*A[i]*B[i];
		int j1=u+1,j2=u+1;for(i=u;i>=l;--i)
		{
			while(j1<=r&&A[j1]<=A[i]) ++j1;while(j2<=r&&B[j2]<=B[i]) ++j2;
			ans+=1ull*A[i]*B[i]*(min(j1,j2)-u-1)+(j1<=j2?(SA[j2-1]-SA[j1-1])*B[i]:A[i]*(SB[j1-1]-SB[j2-1]))+S[r]-S[max(j1,j2)-1];
		}
	}
	void Solve() {int l,r;while(Qt--) ans=0,read(l),read(r),Solve(l,r),writeln(ans);}
}
int main()
{
	freopen("match.in","r",stdin),freopen("match.out","w",stdout);
	int Id,i;for(read(Id),read(n),i=1;i<=n;++i) read(a[i]);for(i=1;i<=n;++i) read(b[i]);read(Qt);
	if(n<=BN) return BF::Solve(),clear(),0;return DC::Solve(),clear(),0;
}
