//Private Eye, dancing with the wind.
#include<bits/stdc++.h>
using namespace std;

#define MAXN 3005
#define MAXN2 250005
#define lgMAXN2 20
#define ull unsigned long long
int a[MAXN2],b[MAXN2];
int T,n,m;

namespace Subtask1{
	ull s[MAXN][MAXN];
	void solve()
	{
		for(int i=1;i<=n;i++)
	 	{
	 		ull maxna=a[i],maxnb=b[i];
	 		s[i][i]=maxna*maxnb;
	 		for(int j=i+1;j<=n;j++)
			{
				maxna=max(maxna,1ull*a[j]);
				maxnb=max(maxnb,1ull*b[j]);
				s[i][j]=s[i][j-1]+maxna*maxnb;
			}
		}
		scanf("%d",&m);
		while(m--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			ull ans=0;
			for(int i=l;i<=r;i++)
				ans+=s[i][r];
			printf("%llu\n",ans);
		}	
	}
}

namespace Subtask2{
	int f[MAXN2][lgMAXN2],f2[MAXN2][lgMAXN2];
	int lg[MAXN2>>1],pos[MAXN2][lgMAXN2],pos2[MAXN2][lgMAXN2];
	int tmp1[MAXN],tmp2[MAXN];
	inline int query1(int l,int r)
	{
		int k=lg[r-l+1];
		if(f[l][k]>f[r-(1<<k)+1][k]) return pos[l][k];
		else return pos[r-(1<<k)+1][k];
	}
	inline int query2(int l,int r)
	{
		int k=lg[r-l+1];
		if(f2[l][k]>f2[r-(1<<k)+1][k]) return pos2[l][k];
		else return pos2[r-(1<<k)+1][k];
	}
	void solve()
	{
		for(int i=2;i<=n;i++)
			lg[i]=lg[i>>1]+1;
		for(int i=1;i<=n;i++)
		{
			f[i][0]=a[i],f2[i][0]=b[i];
			pos[i][0]=pos2[i][0]=i;
		}
		for(int k=1;k<=lg[n];k++)
			for(int i=1;i+(1<<k)-1<=n;i++)
			{
				f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
				if(f[i][k-1]>f[i+(1<<(k-1))][k-1]) pos[i][k]=pos[i][k-1];
				else pos[i][k]=pos[i+(1<<(k-1))][k-1];
				f2[i][k]=max(f2[i][k-1],f2[i+(1<<(k-1))][k-1]);
				if(f2[i][k-1]>f2[i+(1<<(k-1))][k-1]) pos2[i][k]=pos2[i][k-1];
				else pos2[i][k]=pos2[i+(1<<(k-1))][k-1];
			}
		int m;
		scanf("%d",&m);
		while(m--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			ull ans=0;
			for(int i=l;i<=r;i++)
			{
				int cnt1=0,cnt2=0;
				int s1=i,s2=r;
				while(s1<=s2)
				{
					int res=query1(s1,s2);
					tmp1[++cnt1]=res;
					s2=res-1;
				}
				s1=i,s2=r;
				while(s1<=s2)
				{
					int res=query2(s1,s2);
					tmp2[++cnt2]=res;
					s2=res-1;
				}
				for(int j=1;j<=cnt1/2;j++) swap(tmp1[j],tmp1[cnt1+1-j]);
				for(int j=1;j<=cnt2/2;j++) swap(tmp2[j],tmp2[cnt2+1-j]);
				tmp1[++cnt1]=r+1;tmp2[++cnt2]=r+1;
				int now=i,qwq1=1,qwq2=1;
				while(now<=r)
				{
					int nxt=min(tmp1[qwq1+1],tmp2[qwq2+1]);
					ans+=1ull*(nxt-now)*a[tmp1[qwq1]]*b[tmp2[qwq2]];
					now=nxt;
					while(tmp1[qwq1+1]<=now) qwq1++;
					while(tmp2[qwq2+1]<=now) qwq2++;
				}
			}
			printf("%llu\n",ans);
		}
	}
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
 	scanf("%d%d",&T,&n);
 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
 	if(n<=3000) Subtask1::solve();
 	else Subtask2::solve();
}