/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define int long long
#define ull unsigned long long
#define ls x+x
#define rs x+x+1
#define len(a) (int)a.size()
using namespace std;
const int N=3*1e5+100;
int T,n,q,a[N],b[N],ans[N],va[N],vb[N];
int A[N],wa,B[N],wb;
vector <pair<int,int> > p[N];
inline int read()
{
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
namespace seg
{
	int ta[N*4],tb[N*4];
	ull sa[N*4],sb[N*4],sum[N*4];
	void pushup(int x)
	{
		sa[x]=sa[ls]+sa[rs];
		sb[x]=sb[ls]+sb[rs];
		sum[x]=sum[ls]+sum[rs];
	}
	void pushdown(int x,int l,int mid,int r)
	{
		if (ta[x]!=-1)
		{
			sa[ls]=1ull*ta[x]*(mid-l+1);sa[rs]=1ull*ta[x]*(r-mid);
			sum[ls]=sb[ls]*ta[x],sum[rs]=sb[rs]*ta[x];
			ta[ls]=ta[rs]=ta[x];
			ta[x]=-1;
		}
		if (tb[x]!=-1)
		{
			sb[ls]=1ull*tb[x]*(mid-l+1);sb[rs]=1ull*tb[x]*(r-mid);
			sum[ls]=sa[ls]*tb[x],sum[rs]=sa[rs]*tb[x];
			tb[ls]=tb[rs]=tb[x];
			tb[x]=-1;
		}
	}
	void build(int x,int l,int r)
	{
		ta[x]=tb[x]=-1;sa[x]=sb[x]=sum[x]=0;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void change(int x,int l,int r,int ll,int rr,int v,int op)
	{
		if (ll<=l&&rr>=r)
		{
			if (op==0) ta[x]=v,sa[x]=1ull*(r-l+1)*v,sum[x]=sb[x]*v;
			else tb[x]=v,sb[x]=1ull*(r-l+1)*v,sum[x]=sa[x]*v;
			return;
		}
		int mid=(l+r)>>1;pushdown(x,l,mid,r);
		if (ll<=mid) change(ls,l,mid,ll,rr,v,op);
		if (rr>mid) change(rs,mid+1,r,ll,rr,v,op);
		pushup(x);
	}
}
// namespace ment
// {
// 	ull sum[N*4],tag[N*4];
// 	void pushup(int x){sum[x]=sum[ls]+sum[rs];}
// 	void pushdown(int x,int l,int mid,int r)
// 	{
// 		sum[ls]+=tag[x]*(mid-l+1),sum[rs]+=tag[x]*(r-mid);
// 		tag[ls]+=tag[x],tag[rs]+=tag[x];
// 		tag[x]=0;
// 	}
// 	void change(int x,int l,int r,int ll,int rr,ull v)
// 	{
// 		if (ll<=l&&rr>=r)
// 		{
// 			tag[x]+=v;sum[x]+=v*(r-l+1);
// 			return;
// 		}
// 		int mid=(l+r)>>1;pushdown(x,l,mid,r);
// 		if (ll<=mid) change(ls,l,mid,ll,rr,v);
// 		if (rr>mid) change(rs,mid+1,r,ll,rr,v);
// 		pushup(x);
// 	}
// 	ull query(int x,int l,int r,int ll,int rr)
// 	{
// 		if (ll<=l&&rr>=r) return sum[x];
// 		int mid=(l+r)>>1;pushdown(x,l,mid,r);ull ans=0;
// 		if (ll<=mid) ans+=query(ls,l,mid,ll,rr);
// 		if (rr>mid) ans+=query(rs,mid+1,r,ll,rr);
// 		return ans;
// 	}
// }
namespace subtask1
{
	ull solve(int a[],int b[],int n)
	{
		seg::build(1,1,n);
		wa=wb=0;ull ans=0;
		for (int i=1;i<=n;i++)
		{
			while (wa&&a[A[wa]]<a[i]) wa--;
			A[++wa]=i;
			while (wb&&b[B[wb]]<b[i]) wb--;
			B[++wb]=i;
			int ta=A[wa-1]+1,tb=B[wb-1]+1;
			seg::change(1,1,n,ta,i,a[i],0);
			seg::change(1,1,n,tb,i,b[i],1);
			ans+=seg::sum[1];
		}
		return ans;
	}
	int c[N],d[N];
	void solve()
	{
		while (q--)
		{
			int l=read(),r=read();
			for (int i=l;i<=r;i++) c[i-l+1]=a[i],d[i-l+1]=b[i];
			printf("%llu\n",solve(c,d,r-l+1));
		}
	}
}
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	T=read();n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) b[i]=read();
	q=read();
	// if (n*q<=1e7)
	// {
		subtask1::solve();
		return 0;
	// }
	// for (int i=1;i<=q;i++)
	// {
	// 	int l=read(),r=read();
	// 	p[r].emplace_back(l,i);
	// }
	// for (int i=1;i<=n;i++)
	// {
	// 	while (wa&&A[wa]<a[i]) wa--;
	// 	A[++wa]=a[i];
	// 	while (wb&&B[wb]<b[i]) wb--;
	// 	B[++wb]=b[i];
	// 	int ta=A[wa-1]+1,tb=B[wb-1]+1;
		
	// }
}