#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=250010;
int n,q,a[N],b[N];
namespace brute{
	const int N=3010;
	ull p[N][N];
	void solve()
	{
		for(int i=1;i<=n;i++)
		{
			int mx=0,my=0;
			for(int j=i;j<=n;j++)
			{
				mx=max(mx,a[j]),my=max(my,b[j]);
				p[i][j]=(ull)mx*my;
			}
		}
		for(int i=n;i;i--)
			for(int j=i+1;j<=n;j++) p[i][j]+=p[i][j-1]+p[i+1][j]-p[i+1][j-1];
		while(q --> 0)
		{
			int l,r;scanf("%d%d",&l,&r);
			printf("%llu\n",p[l][r]);
		}
	}
}
namespace sub{
	int prea[N],sufa[N],preb[N],sufb[N];
	ull ans=0;
	void solve(int l,int r)
	{
		if(l>r) return;
		int p=max_element(a+l,a+r+1)-a;
		solve(l,p-1),solve(p+1,r);
		static int tl[N],tr[N];int cl=0,cr=0;
		tl[0]=tr[0]=p;
		for(int i=preb[p];i>=l;i=preb[i]) tl[++cl]=i;
		for(int i=sufb[p];i<=r;i=sufb[i]) tr[++cr]=i;
		tl[++cl]=l-1,tr[++cr]=r+1;
		int pl=1,pr=1;ans+=(ull)(p-tl[1])*(tr[1]-p)*a[p]*b[p];
		while(pl<cl || pr<cr)
		{
			if(pl<cl && (pr==cr || b[tl[pl]]<b[tr[pr]]))
			{
				ans+=(ull)(tl[pl]-tl[pl+1])*(tr[pr]-p)*a[p]*b[tl[pl]];
				pl++;
			}
			else
			{
				ans+=(ull)(p-tl[pl])*(tr[pr+1]-tr[pr])*a[p]*b[tr[pr]];
				pr++;
			}
		}
	}
	void calc()
	{
		for(int i=1;i<=n;i++)
		{
			for(prea[i]=i-1;prea[i] && a[prea[i]]<a[i];prea[i]--);
			for(sufa[i]=i+1;sufa[i]<=n && a[sufa[i]]<a[i];sufa[i]++);
			for(preb[i]=i-1;preb[i] && b[preb[i]]<b[i];preb[i]--);
			for(sufb[i]=i+1;sufb[i]<=n && b[sufb[i]]<b[i];sufb[i]++);
		}
		for(int i=1;i<=q;i++)
		{
			int l,r;scanf("%d%d",&l,&r);
			ans=0;
			solve(l,r);
			printf("%llu\n",ans);
		}
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%*d%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	scanf("%d",&q);
	if(n<=3000){brute::solve();return 0;}
	sub::calc();
	return 0;
}
