// Fresh Peach Heart Shower
#include <bits/stdc++.h>
#define pb push_back
#define MP std::make_pair
#define ALL(x) (x).begin(),(x).end()
#define mem(x,y) memset(x,y,sizeof(x))
#ifdef _LOCAL_
#define dprintf(x...) fprintf(stderr,x)
#else
#define dprintf(x...) 42
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
typedef std::vector<int > poly;
typedef std::pair<int,int > pii;
void setIn(std::string s){freopen(s.c_str(),"r",stdin);}
void setOut(std::string s){freopen(s.c_str(),"w",stdout);}
void setIO(std::string s){setIn(s+".in"),setOut(s+".out");}
template <class t> inline bool ckmin(t&x,t y){if(x>y)return x=y,1;return 0;}
template <class t> inline bool ckmax(t&x,t y){if(x<y)return x=y,1;return 0;}
inline int lowbit(int x){return x&(-x);}
typedef unsigned long long ull;
const int MaxN=5e5+50;
int n,q;
struct Tree
{
	ull a[MaxN];
	int ls[MaxN],rs[MaxN],anc[MaxN],root;
	int up[21][MaxN],LG[MaxN],dep[MaxN],dfn[MaxN],dfncnt;
	int Lb[MaxN],Rb[MaxN];
	ull dp[MaxN];
	ull siz[MaxN];
	void dfs(int u,int l=1,int r=n)
	{
		Lb[u]=l,Rb[u]=r;
		dep[u]=dep[anc[u]]+1;
		up[0][dfn[u]=++dfncnt]=u;
		siz[u]=1;
		if(ls[u])
		{
			anc[ls[u]]=u;
			dfs(ls[u],l,ls[u]),siz[u]+=siz[ls[u]];
			up[0][++dfncnt]=u;
			dp[u]+=dp[ls[u]];
		}
		if(rs[u])
		{
			anc[rs[u]]=u;
			dfs(rs[u],rs[u],r),siz[u]+=siz[rs[u]];
			up[0][++dfncnt]=u;
			dp[u]+=dp[rs[u]];
		}
		dp[u]+=a[u]*(siz[ls[u]]+1)*(siz[rs[u]]+1);
	}
	int min(int x,int y){return dep[x]<dep[y]?x:y;}
	void init()
	{
		poly st(n+5);
		int tp=0;
		rep(i,1,n)
		{
			while(tp&&a[st[tp]]<a[i])ls[i]=st[tp--];
			if(tp)rs[st[tp]]=i;
			else root=i;
			st[++tp]=i;
		}
		dfs(root);
		rep(i,2,dfncnt)LG[i]=LG[i>>1]+1;
		rep(k,1,20)for(int i=1;i+(1<<k)-1<=dfncnt;++i)
			up[k][i]=min(up[k-1][i],up[k-1][i+(1<<~-k)]);
	}
	int lca(int u,int v)
	{
		u=dfn[u],v=dfn[v];if(u>v)std::swap(u,v);
		int k=LG[v-u+1];
		return min(up[k][u],up[k][v-(1<<k)+1]);
	}
	ull QueryLeft(int u,int goal)
	{
		if(u==goal)return 0;
		int st=u;
		ull ans=0,s=1;
		ans+=dp[ls[u]],s+=siz[ls[u]];
		ans+=a[u]*s;
		while(anc[u]^goal)
		{
			u=anc[u];
			if(u<st)
			{
				ans+=a[u]*(s+1)*(siz[ls[u]]+1)+dp[ls[u]];
				s+=1+siz[ls[u]];
			}
		}
		return ans;
	}
	ull QueryRight(int u,int goal)
	{
		if(u==goal)return 0;
		int st=u;
		ull ans=0,s=1;
		ans+=dp[rs[u]],s+=siz[rs[u]];
		ans+=a[u]*s;
		while(anc[u]^goal)
		{
			u=anc[u];
			if(u>st)
			{
				ans+=a[u]*(s+1)*(siz[rs[u]]+1)+dp[rs[u]];
				s+=1+siz[rs[u]];
			}
		}
		return ans;
	}
	ull QuerySum(int l,int r)
	{
		int g=lca(l,r);
		return QueryRight(l,g)+QueryLeft(r,g)+a[g]*(g-l+1)*(r-g+1);
	}
	ull max(int l,int r)
	{
		return a[lca(l,r)];
	}
}A,B;
ull sdp[MaxN];
void dfs(int u)
{
	if(A.ls[u])
	{
		dfs(A.ls[u]);
		sdp[u]+=sdp[A.ls[u]];
	}
	if(A.rs[u])
	{
		dfs(A.rs[u]);
		sdp[u]+=sdp[A.rs[u]];
	}
	sdp[u]+=A.a[u]*B.QuerySum(A.Lb[u],A.Rb[u]);
}

/*
ull QueryLeft(int u,int goal)
{
	if(u==goal)return 0;
	int st=u;
	ull ans=0,s=B.a[u];
	ans+=sdp[A.ls[u]],s+=B.dp[A.ls[u]];
	ans+=A.a[u]*s;
	while(A.anc[u]^goal)
	{
		u=A.anc[u];
		if(u<st)
		{
			ans+=A.a[u]*(s+B.a[u])*(B.dp[A.ls[u]]+B.a[u])+sdp[A.ls[u]];
			s+=B.a[u]+B.dp[A.ls[u]];
		}
	}
	return ans;
}

ull QueryRight(int u,int goal)
{
	if(u==goal)return 0;
	int st=u;
	ull ans=0,s=1;
	ans+=dp[rs[u]],s+=siz[rs[u]];
	ans+=a[u]*s;
	while(anc[u]^goal)
	{
		u=anc[u];
		if(u>st)
		{
			ans+=a[u]*(s+1)*(siz[rs[u]]+1)+dp[rs[u]];
			s+=1+siz[rs[u]];
		}
	}
	return ans;
}
ull QuerySum(int l,int r)
{
	int g=lca(l,r);
	return QueryRight(l,g)+QueryLeft(r,g)+a[g]*(g-l+1)*(r-g+1);
}
*/
namespace BF
{
	int Amx[3050][3050];
	int Bmx[3050][3050];
	ull dp[3050][3050];
	signed main()
	{
		rep(i,1,n)
		{
			Amx[i][i]=A.a[i];
			rep(j,i+1,n)
				Amx[i][j]=A.a[j],
				ckmax(Amx[i][j],Amx[i][j-1]);
		}
		rep(i,1,n)
		{
			Bmx[i][i]=B.a[i];
			rep(j,i+1,n)
				Bmx[i][j]=B.a[j],
				ckmax(Bmx[i][j],Bmx[i][j-1]);
		}
		rep(i,1,n)rep(j,i,n)dp[i][j]=1uLL*Amx[i][j]*Bmx[i][j];
		rep(len,2,n)rep(i,1,n-len+1)
		{
			int j=i+len-1;
			dp[i][j]+=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
		}
		int l,r;
		while(q--)
		{
			std::cin>>l>>r;
			std::cout<<dp[l][r]<<'\n';
		}
		return 0;
	}
}
poly Ago[MaxN],Bgo[MaxN];
ull Ask(int l,int r)
{
	ull ans=0;
	rep(i,l,r)
	{
		poly dr;
		for(auto j:Ago[i])dr.pb(j);
		for(auto j:Bgo[i])dr.pb(j);
		dr.pb(l);
		dr.pb(r+1);
		std::sort(ALL(dr));
		rep(j,0,(int)dr.size()-2)
		{
			int p=dr[j],q=dr[j+1];
			if(p==r)break;
			ans+=A.max(i,p)*B.max(i,p)*(q-p);
		}
	}
	return ans;
}
signed main(void)
{
#ifndef _LOCAL_
	std::ios::sync_with_stdio(false),std::cin.tie(0);
#endif
	
	setIO("match");

	int tid;std::cin>>tid>>n;
	rep(i,1,n)std::cin>>A.a[i];
	rep(i,1,n)std::cin>>B.a[i];
	A.init(),B.init();
	std::cin>>q;
	if(n<=3000&&q<=3000)return BF::main();
	poly st(n+5);
	int tp=0;
	per(i,n,1)
	{
		while(tp&&A.a[st[tp]]<A.a[i])--tp;
		Ago[tp]=st;
		st[++tp]=i;
	}
	tp=0;
	per(i,n,1)
	{
		while(tp&&B.a[st[tp]]<B.a[i])--tp;
		Bgo[tp]=st;
		st[++tp]=i;
	}
	int l,r;
	while(q--)
	{
		std::cin>>l>>r;
		std::cout<<Ask(l,r)<<'\n';
	}
	return 0;
}


