#include<bits/stdc++.h>
#define maxn 250005
#define ll long long 
#define ull unsigned long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x) {
	x=0;char ch=getchar();int f=1;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
}
int a[maxn],b[maxn],n,m;
struct yyy{
	ull sum,suma,sumb;
	int lazya,lazyb;
}f[maxn<<2];
namespace BL{
	inline void Pushup(int rt) {
		f[rt].sum=f[rt<<1].sum+f[rt<<1|1].sum;
		f[rt].suma=f[rt<<1].suma+f[rt<<1|1].suma;
		f[rt].sumb=f[rt<<1].sumb+f[rt<<1|1].sumb;
	}
	inline void Pushdown(int l,int r,int rt) {
		int mid=l+r>>1;
		if (f[rt].lazya!=-1&&f[rt].lazyb!=-1) {
			f[rt<<1].suma=1ull*(mid-l+1)*f[rt].lazya;f[rt<<1].lazya=f[rt].lazya;
			f[rt<<1|1].suma=1ull*(r-mid)*f[rt].lazya;f[rt<<1|1].lazya=f[rt].lazya;
			f[rt<<1].sumb=1ull*(mid-l+1)*f[rt].lazyb;f[rt<<1].lazyb=f[rt].lazyb;
			f[rt<<1|1].sumb=1ull*(r-mid)*f[rt].lazyb;f[rt<<1|1].lazyb=f[rt].lazyb;
			f[rt<<1].sum=1ull*(mid-l+1)*f[rt].lazya*f[rt].lazyb;
			f[rt<<1|1].sum=1ull*(r-mid)*f[rt].lazya*f[rt].lazyb;
			f[rt].lazya=f[rt].lazyb=-1;
		} 
		else if (f[rt].lazya!=-1) {
			f[rt<<1].suma=1ull*(mid-l+1)*f[rt].lazya;f[rt<<1].lazya=f[rt].lazya;
			f[rt<<1|1].suma=1ull*(r-mid)*f[rt].lazya;f[rt<<1|1].lazya=f[rt].lazya;
			f[rt<<1].sum=1ull*f[rt<<1].sumb*f[rt].lazya;
			f[rt<<1|1].sum=1ull*f[rt<<1|1].sumb*f[rt].lazya;
			f[rt].lazya=-1;
		}
		else if (f[rt].lazyb!=-1) {
			f[rt<<1].sumb=1ull*(mid-l+1)*f[rt].lazyb;f[rt<<1].lazyb=f[rt].lazyb;
			f[rt<<1|1].sumb=1ull*(r-mid)*f[rt].lazyb;f[rt<<1|1].lazyb=f[rt].lazyb;
			f[rt<<1].sum=1ull*f[rt<<1].suma*f[rt].lazyb;
			f[rt<<1|1].sum=1ull*f[rt<<1|1].suma*f[rt].lazyb;
			f[rt].lazyb=-1;
		}
	}
	inline void Update1(int l,int r,int rt,int head,int tail,int k) {
		if (head<=l&&r<=tail) {
			f[rt].lazya=k;f[rt].suma=1ull*(r-l+1)*k,f[rt].sum=1ull*k*f[rt].sumb;
			return ;
		}
		int mid=l+r>>1;
		Pushdown(l,r,rt);
		if (head<=mid) Update1(l,mid,rt<<1,head,tail,k);
		if (tail>mid)  Update1(mid+1,r,rt<<1|1,head,tail,k);
		Pushup(rt);
	}
	inline void Update2(int l,int r,int rt,int head,int tail,int k) {
		if (head<=l&&r<=tail) {
			f[rt].lazyb=k;f[rt].sumb=1ull*(r-l+1)*k,f[rt].sum=1ull*k*f[rt].suma;
			return ;
		}
		int mid=l+r>>1;
		Pushdown(l,r,rt);
		if (head<=mid) Update2(l,mid,rt<<1,head,tail,k);
		if (tail>mid)  Update2(mid+1,r,rt<<1|1,head,tail,k);
		Pushup(rt);
	}
	inline ull Query(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return f[rt].sum;
		int mid=l+r>>1;ull tmp=0;Pushdown(l,r,rt);
		if (head<=mid) tmp+=Query(l,mid,rt<<1,head,tail);
		if (tail>mid)  tmp+=Query(mid+1,r,rt<<1|1,head,tail);
		return tmp;
	}
	int L[maxn],R[maxn],stac[maxn];
	int L2[maxn];
	inline void main(void) {
		int i,tot=0,l,r;ull ans=0;
		Update1(1,n,1,1,n,0);
		Update2(1,n,1,1,n,0);
		for (i=1;i<=n;i++) {
			while (tot&&a[stac[tot]]<=a[i]) tot--;
			L[i]=stac[tot]+1;stac[++tot]=i;
		}
		tot=0;
//		for (i=n;i>=1;i--) {
//			while (tot&&a[stac[tot]]<=a[i]) tot--;
//			if (tot) R[i]=stac[tot]-1;else R[i]=n;
//			stac[++tot]=i;
//		}
		for (i=1;i<=n;i++) {
			while (tot&&b[stac[tot]]<=b[i]) tot--;
			L2[i]=stac[tot]+1;stac[++tot]=i;
		}
		while (m--) {
			read(l);read(r);
			Update1(1,n,1,l,r,0);
			Update2(1,n,1,l,r,0);
			
			ans=0;
			for (i=l;i<=r;i++) {
				Update1(1,n,1,max(L[i],l),i,a[i]);
				Update2(1,n,1,max(L2[i],l),i,b[i]);
				ans+=Query(1,n,1,l,i);
			}
			printf("%llu\n",ans);
		}
	} 
}
namespace BL2{
	int fa[maxn],ls[maxn],rs[maxn],bb[maxn],g[maxn];
	vector<ull>Max[maxn];
	struct BIT{
		#define lowbit(x) ((x)&(-x))
		ull f[maxn];
		inline void clear(int x) {for (int i=0;i<=x;i++) f[x]=0;}
		inline void add(int x,int y) {for (;x<=n;x+=lowbit(x)) f[x]+=y;}
		inline int query(int x) {int sum=0;for (;x;x-=lowbit(x)) sum+=f[x];}
	}t1,t2;
	int L[maxn],R[maxn],id[maxn],tl[maxn],tr[maxn];
	ull w[maxn],sumw[maxn],ans;
	inline int build(int l,int r) {
		int i,maxx=0,x;
		for (i=l;i<=r;i++) if (!maxx||a[maxx]<a[i]) maxx=i;
		L[x=maxx]=l;R[x]=r;
		Max[x].resize(r-l+2);suf[x].resize(r-l+2);
		int mid=x-l+1;Max[x][mid]=bb[x];
		for (i=mid+1;i<=r-l+1;i++) Max[x][i]=max(Max[x][i-1],1ull*bb[i+l-1]);
		for (i=mid-1;i>=1;i--) Max[x][i]=max(Max[x][i+1],1ull*bb[i+l-1]);
		int now=mid,sum1=0,sum2=0;ull sum=0;
		for (i=mid;i>=1;i--) {
			while (Max[x][i]<=) 
		} 
		w[x]=sum*a[x];
		
		if (l<maxx) ls[x]=build(l,maxx-1),fa[ls[x]]=x;
		if (maxx<r) rs[x]=build(r,maxx+1),fa[rs[x]]=x; 
		sumw[x]=w[x]+sumw[ls[x]]+sumw[rs[x]];
		return x;
	}
	inline int getfa(int x,int head,int tail) {
		while (!(L[x]<=head&&tail<=R[x])) x=fa[x];
		return x;
	}
	struct node{
		int l,r,id;
		node(int b=0,int c=0,int d) {l=b;r=c;id=d;}
	};
	vector<node>Q[maxn];
	int Ans[maxn];
	inline void solve(int x,int id,int head,int tail) {
		if (L[x]==R[x]) return ans+=sumw[x],void();
		if (L[x]<=head&&tail<=R[x]) {
			Q[x].push_back(node(head-L[x]+1,tail-L[x]+1,id));
//			ans+=suf[x][head-L[x]+1]*suf[x][tail-L[x]+1]*a[x];
			solve(ls[x],head,tail);
			solve(rs[x],head,tail);
		}
		else if (L[x]<=head) {
			Q[x].push_back(node(head-L[x]+1,R[x]-L[x]+1,id));
//			ans+=suf[x][head-L[x]+1]*suf[x][R[x]-L[x]+1]*a[x]+sumw[rs[x]];
			if (head<x) solve(ls[x],head,tail);
		}
		else if (tail<=R[x]) {
			Q[x].push_back(node(1,tail-L[x]+1,id));
//			ans+=suf[x][1]*suf[x][tail-L[x]+1]*a[x]+sumw[ls[x]];
			solve(rs[x],head,tail);
		}
	}
	inline void main(void) {
		int l,r,x;
		for (i=1;i<=n;i++) g[++tot]=b[i];
		sort(g+1,g+1+tot);tot=unique(g+1,g+1+tot)-g-1;
		for (i=1;i<=n;i++) bb[i]=lower_bound(g+1,g+1+tot,b[i])-g;  
		build(1,n);
//		for (int i=1;i<=n;i++) printf("%d : %d %d %d %d %llu\n",i,ls[i],rs[i],L[i],R[i],sumw[i]);
		return ;
		for (i=1;i<=m;i++) {
			read(l);read(r);ans=0;
			x=getfa(l,l,r);
			solve(x,i,l,r);
			printf("%llu\n",ans); 
		}
		return ;
	} 
}
signed main(void) {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int i,T;
	read(T);read(n);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) read(b[i]);
	read(m);
	if (T<=13) BL::main();else 
	BL2::main();
	return 0;
}