#include<bits/stdc++.h>
#define Pc(x) putchar(x)
#define PB push_back
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
using namespace std;using ll=long long;using ull=unsigned long long;
const int N=2.5e5+5,M=N*4+5,eps=1e-5,INF=1e6,mod=998244353;
int sh,T,n,m,x,y,L[N],st[N],A[N],B[N];ull Ans[N];
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	int Si[M],p[M];ull f[M],g1[M],g2[M],Sum[M];
	void Up(int v){Sum[v]=Sum[ls]+Sum[rs];f[v]=f[ls]+f[rs];}
	void BD(int l=1,int r=n,int v=1){Si[v]=r-l+1;p[v]=-1;if(l==r) return;int m=l+r>>1;BD(l,m,ls);BD(m+1,r,rs);Up(v);}
	void Pg(int v,ull G1,ull G2){if(v>1e6) return;g1[v]+=G1;g2[v]+=G2;f[v]+=Sum[v]*G1+Si[v]*G2;}
	void Pp(int v,int P){
		if(p[v]==-1){
			Pg(ls,g1[v],g2[v]);Pg(rs,g1[v],g2[v]);g1[v]=g2[v]=0;
		}else g2[v]-=g1[v]*(P-p[v]);
		p[v]=P;Sum[v]=1llu*P*Si[v];
	}
	void P(int v){~p[v]&&(Pp(ls,p[v]),Pp(rs,p[v]),p[v]=-1);(g1[v]||g2[v])&&(Pg(ls,g1[v],g2[v]),Pg(rs,g1[v],g2[v]),g1[v]=g2[v]=0);}
	void Ins(int x,int y,int w,int l=1,int r=n,int v=1){if(x<=l&&r<=y) return Pp(v,w);P(v);int m=l+r>>1;x<=m&&(Ins(x,y,w,l,m,ls),0);y>m&&(Ins(x,y,w,m+1,r,rs),0);Up(v);}
	void Push(int x,int y,ull z,int l=1,int r=n,int v=1){if(x<=l&&r<=y) return Pg(v,z,0);P(v);int m=l+r>>1;x<=m&&(Push(x,y,z,l,m,ls),0);y>m&&(Push(x,y,z,m+1,r,rs),0);Up(v);}
	ull Qry(int x,int y,int l=1,int r=n,int v=1){if(x<=l&&r<=y)return f[v];int m=l+r>>1;P(v);return (x<=m?Qry(x,y,l,m,ls):0)+(y>m?Qry(x,y,m+1,r,rs):0);}
	#undef ls
	#undef rs
}
struct Ques{int l,w;};vector<Ques> S[N];
int main(){
	freopen("match.in","r",stdin);freopen("match.out","w",stdout);
	int i,j,T;scanf("%d%d",&T,&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);
	for(i=1;i<=n;i++) {while(sh&&B[st[sh]]<B[i]) sh--;L[i]=st[sh]+1;st[++sh]=i;}
	Tree::BD();scanf("%d",&m);for(i=1;i<=m;i++) scanf("%d%d",&x,&y),S[y].PB((Ques){x,i});
	st[sh=0]=0;for(i=1;i<=n;i++){
		/*assert(L[i]<=i);*/Tree::Ins(L[i],i,B[i]);
		while(sh&&A[st[sh]]<A[i]) sh--;st[++sh]=i;
		for(j=1;j<=sh;j++) Tree::Push(st[j-1]+1,st[j],A[st[j]]);
		//printf("Degub %llu\n",Tree::Qry(1,i));
		for(Ques j:S[i]) Ans[j.w]=Tree::Qry(j.l,i);
	}for(i=1;i<=m;i++) printf("%llu\n",Ans[i]);
}