#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=250000;
int opt,n,a[N+5],b[N+5],q;
int st1[N+5],top1,st2[N+5],top2;
ull ans;
struct Node{
	int l,r;
	ull s1,s2,s,lazy1,lazy2;
}tree[4*N+5];
inline void push_down(int root){
	if(tree[root].lazy1==0&&tree[root].lazy2==0)return ;
	if(tree[root].lazy1>0){
		tree[root<<1].s1=1llu*(tree[root<<1].r-tree[root<<1].l+1)*tree[root].lazy1;
		tree[root<<1|1].s1=1llu*(tree[root<<1|1].r-tree[root<<1|1].l+1)*tree[root].lazy1;
		tree[root<<1].s=tree[root<<1].s2*tree[root].lazy1;
		tree[root<<1|1].s=tree[root<<1|1].s2*tree[root].lazy1;
		tree[root<<1].lazy1=tree[root<<1|1].lazy1=tree[root].lazy1;
		tree[root].lazy1=0;
	}
	if(tree[root].lazy2>0){
		tree[root<<1].s2=1llu*(tree[root<<1].r-tree[root<<1].l+1)*tree[root].lazy2;
		tree[root<<1|1].s2=1llu*(tree[root<<1|1].r-tree[root<<1|1].l+1)*tree[root].lazy2;
		tree[root<<1].s=tree[root<<1].s1*tree[root].lazy2;
		tree[root<<1|1].s=tree[root<<1|1].s1*tree[root].lazy2;
		tree[root<<1].lazy2=tree[root<<1|1].lazy2=tree[root].lazy2;
		tree[root].lazy2=0;
	}
}
inline void push_up(int root){
	tree[root].s1=tree[root<<1].s1+tree[root<<1|1].s1;
	tree[root].s2=tree[root<<1].s2+tree[root<<1|1].s2;
	tree[root].s=tree[root<<1].s+tree[root<<1|1].s;
}
void build(int root,int l,int r){
	tree[root].l=l,tree[root].r=r;
	tree[root].s1=tree[root].s2=tree[root].s=0;
	tree[root].lazy1=tree[root].lazy2=0;
	if(l==r)return ;
	build(root<<1,l,l+r>>1);
	build(root<<1|1,(l+r>>1)+1,r);
}
void modify1(int root,int l,int r,int x){
	if(tree[root].l>=l&&tree[root].r<=r){
		tree[root].s1=1llu*(tree[root].r-tree[root].l+1)*x;
		tree[root].s=tree[root].s2*x;
		tree[root].lazy1=x;
		return ;
	}
	push_down(root);
	if(tree[root<<1].r>=l)modify1(root<<1,l,r,x);
	if(tree[root<<1|1].l<=r)modify1(root<<1|1,l,r,x);
	push_up(root);
}
void modify2(int root,int l,int r,int x){
	if(tree[root].l>=l&&tree[root].r<=r){
		tree[root].s2=1llu*(tree[root].r-tree[root].l+1)*x;
		tree[root].s=tree[root].s1*x;
		tree[root].lazy2=x;
		return ;
	}
	push_down(root);
	if(tree[root<<1].r>=l)modify2(root<<1,l,r,x);
	if(tree[root<<1|1].l<=r)modify2(root<<1|1,l,r,x);
	push_up(root);
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int l,r;
	scanf("%d%d",&opt,&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&l,&r);
		ans=0;
		build(1,l,r);
		top1=top2=0;
		st1[0]=st2[0]=l-1;
		for(int i=l;i<=r;i++){
			while(top1&&a[st1[top1]]<a[i])top1--;
			while(top2&&b[st2[top2]]<b[i])top2--;
			modify1(1,st1[top1]+1,i,a[i]);
			modify2(1,st2[top2]+1,i,b[i]);
			ans+=tree[1].s;
			st1[++top1]=i;
			st2[++top2]=i;
		}
		printf("%llu\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
