#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

typedef unsigned long long ull;
const int M=250005;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,q,a[M],b[M];

namespace P8
{
	void solve()
	{
		q=read();
		for(int qq=1,l,r;qq<=q;qq++)
		{
			l=read(),r=read();ull ans=0;
			for(int i=l;i<=r;i++)
			{
				int mxa=0,mxb=0;
				for(int j=i;j<=r;j++)
				{
					Max(mxa,a[j]),Max(mxb,b[j]);
					ans+=mxa*mxb;
				}
			}
			printf("%llu\n",ans);
		}
	}
}
namespace P20
{
	const int N=3005;
	int stk[N],top,L[N],R[N];
	ull to[N][N],sum[N][N];
	void solve()
	{
		top=0,stk[0]=0;
		for(int i=0;i<=n+1;i++)L[i]=R[i]=0;
		for(int i=1;i<=n;i++)
		{
			while(top&&a[i]>a[stk[top]])top--;
			L[i]=stk[top]+1;stk[++top]=i;
		}
		top=0,stk[0]=n+1;
		for(int i=n;i>0;i--)
		{
			while(top&&a[i]>a[stk[top]])top--;
			R[i]=stk[top]-1;stk[++top]=i;
		}
//		for(int i=1;i<=n;i++)
//			printf("%d %d\n",L[i],R[i]);
		for(int r=1;r<=n;r++)
		{
			int mx=b[r];to[r][r]=b[r];
			for(int l=r-1;l>0;l--)
			{
				Max(mx,b[l]);
				to[l][r]=to[l+1][r]+mx;
			}
		}
		for(int i=1;i<=n;i++)
		{
			sum[i][i]=to[i][i];
			for(int j=i;j<=n;j++)
				sum[i][j]=sum[i][j-1]+to[i][j];
		}
		q=read();
		for(int qq=1,l,r;qq<=q;qq++)
		{
			l=read(),r=read();ull ans=0;
			for(int i=l,x,y;i<=r;i++)
			{
				x=max(l,L[i]),y=min(r,R[i]);
				ans+=1ull*a[i]*(sum[x][y]-sum[x][i-1]-sum[i+1][y]);
			}
			printf("%llu\n",ans);
		}
	}
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	int cas=read();n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	
	if(n<=30&&q<=30)P8::solve();
	else if(n<=3000&&q<=3000)P20::solve();
	else ;
	
	return 0;
}
/*
0 5
1 4 5 3 2
2 3 1 4 5
*/
