#include<bits/stdc++.h>
#define elif else if
#define pc putchar(' ')
#define pn puts("")
#define rep(i,l,r) for(int i=(l),j=(r);i<=j;++i)
#define per(i,r,l) for(int i=(r),j=(l);i>=j;--i)
#define int unsigned long long
#define N 250005
#define M 1000005
#define A 0x3f3f3f3f
using namespace std;
int read(){int ret=0,b=1,c=getchar();while(!isdigit(c))b=c=='-'?-1:1,c=getchar();while(isdigit(c))ret=ret*10+c-'0',c=getchar();return ret*b;}
void wr(int x){if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10+'0');return;}
void wrc(int x){wr(x),pc;return;}
void wrn(int x){wr(x),pn;return;}
int Min(int x,int y){return x<=y?x:y;}
int Max(int x,int y){return x>=y?x:y;}
void Swap(int &x,int &y){x^=y,y^=x,x^=y;return;}
int n,m,q,ans,a[N],b[N];
struct stable
{
	int st[N][31],lg[N];
	bool flag;
	void init()
	{
		lg[1]=0;
		rep(i,2,n)
			lg[i]=lg[i>>1]+1;
		rep(i,1,n)
			st[i][0]=flag?a[i]:b[i];
		rep(i,1,30)
			for(int t=1;t+(1<<i)-1<=n;++t)
				st[t][i]=Max(st[t][i-1],st[t+(1<<i-1)][i-1]);
		return;
	}
	int query(int x,int y)
	{
		int z=lg[y-x+1];return Max(st[x][z],st[y-(1<<z)+1][z]);
	}
}ma,mb;
struct ld
{
	int x,y,v,s1,s2;
	void init()
	{
		x=y=v=0;return;
	}
	friend ld operator + (const ld &x,const ld &y)
	{
		ld z;z.x=Min(x.x,y.x);
		z.y=Min(x.y,y.y);
		z.v=x.v+y.v;
		z.s1=x.s1+y.s1;
		z.s2=x.s2+y.s2;
		return z;
	}
};
struct segment
{
	ld tree[M];int lazy[M][2];
	void cal(int k,int l,int r,int v1,int v2)
	{
		if(v1!=-1&&v2!=-1)
		{
			tree[k].x=v1;
			tree[k].y=v2;
			tree[k].v=(r-l+1)*v1*v2;
			tree[k].s1=(r-l+1)*v1;
			tree[k].s2=(r-l+1)*v2;
			lazy[k][0]=v1;
			lazy[k][1]=v2;
		}
		elif(v1!=-1)
		{
			tree[k].x=v1;
			tree[k].v=v1*tree[k].s2;
			tree[k].s1=(r-l+1)*v1;
			lazy[k][0]=v1;
		}
		else
		{
			tree[k].y=v2;
			tree[k].v=v2*tree[k].s1;
			tree[k].s2=(r-l+1)*v2;
			lazy[k][1]=v2;
		}
		return;
	}
	void pushup(int k)
	{
		int left=k<<1,right=k<<1|1;
		tree[k]=tree[left]+tree[right];return;
	}
	void pushdown(int k,int l,int r)
	{
		int mid=l+r>>1,left=k<<1,right=k<<1|1;
		if(lazy[k][0]!=-1||lazy[k][1]!=-1)
		{
			cal(left,l,mid,lazy[k][0],lazy[k][1]);
			cal(right,mid+1,r,lazy[k][0],lazy[k][1]);
			lazy[k][0]=lazy[k][1]=-1;
		}
		return;
	}
	int query(int k,int l,int r,int x,int y)
	{
		int mid=l+r>>1,left=k<<1,right=k<<1|1;
		if(x<=l&&r<=y)
			return tree[k].v;
		pushdown(k,l,r);
		if(y<=mid)
			return query(left,l,mid,x,y);
		if(x>mid)
			return query(right,mid+1,r,x,y);
		return query(left,l,mid,x,y)+query(right,mid+1,r,x,y);
	}
	void update(int k,int l,int r,int x,int y,int v1,int v2)
	{
		int mid=l+r>>1,left=k<<1,right=k<<1|1;
		if(x<=l&&r<=y)
			return cal(k,l,r,v1,v2);
		pushdown(k,l,r);
		if(x<=mid)
			update(left,l,mid,x,y,v1,v2);
		if(y>mid)
			update(right,mid+1,r,x,y,v1,v2);
		pushup(k);return;
	}
	int ask(int k,int l,int r,int x,bool op)
	{
		int mid=l+r>>1,left=k<<1,right=k<<1|1;
		if(l==r)
			return op?tree[k].x:tree[k].y;
		pushdown(k,l,r);
		if(x<=mid)
			return ask(left,l,mid,x,op);
		return ask(right,mid+1,r,x,op);
	}
	int search(int l,int r,int x,int y,bool op)
	{
		int mid,z=y;
		while(l<=r)
		{
			mid=l+r>>1;
			if(ask(1,1,n,mid,op)>x)
				l=mid+1;
			else
				z=mid,r=mid-1;
		}
		return z;
	}
}S;
namespace solve1
{
	void solve()
	{
		int x,y;
		rep(i,1,q)
		{
			x=read(),y=read(),ans=0;
			rep(t,x,y)
				rep(k,t,y)
					ans+=ma.query(t,k)*mb.query(t,k);
			wrn(ans);
		}
		return;
	}
}
namespace solve2
{
	void cal(int x,int y)
	{
		int lx,ly;ans=0,S.update(1,1,n,x,y,0,0);
		rep(i,x,y)
		{
			lx=S.search(x,i,a[i],i,true);
			ly=S.search(x,i,b[i],i,false);
			S.update(1,1,n,lx,i,a[i],-1);
			S.update(1,1,n,ly,i,-1,b[i]);
			ans+=S.query(1,1,n,x,i);
		}
		wrn(ans);return;
	}
	void solve()
	{
		int x,y,z,lt;
		rep(i,1,q)
			x=read(),y=read(),cal(x,y);
		return;
	}
}
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int x,y,z,T,id;id=read(),n=read();
	rep(i,1,n)
		a[i]=read();
	rep(i,1,n)
		b[i]=read();
	q=read(),ma.flag=true,ma.init(),mb.init();
	if(n<=30)
		solve1::solve();
	elif(n<=3000)
		solve2::solve();
	fclose(stdin),fclose(stdout);return 0;
}
