#include <bits/stdc++.h>
#define ull unsigned long long
#define ls(p) 2*p
#define rs(p) 2*p+1
using namespace std;

const int N=3005;
const int M=3e5+5;

int n,q;
ull cnt[N][N];
int a[M];
int b[M];
int c[N][N];
int d[N][N];
int T;
int la[M];
int lb[M];
int st[M];
int top;
ull sum[M*4];
ull suma[M*4];
ull sumb[M*4];
ull taga[M*4];
ull tagb[M*4];

void push_down(int p,int l,int r) {
	int mid=(l+r)>>1;
	if(taga[p]!=0) {
		taga[ls(p)]+=taga[p];
		suma[ls(p)]+=(mid-l+1)*taga[p];
		sum[ls(p)]+=taga[p]*sumb[ls(p)];
		
		taga[rs(p)]+=taga[p];
		suma[rs(p)]+=(r-mid)*taga[p];
		sum[rs(p)]+=taga[p]*sumb[rs(p)];
	}
	if(tagb[p]!=0) {
		tagb[ls(p)]+=tagb[p];
		sumb[ls(p)]+=(mid-l+1)*tagb[p];
		sum[ls(p)]+=tagb[p]*suma[ls(p)];
		
		tagb[rs(p)]+=tagb[p];
		sumb[rs(p)]+=(r-mid)*tagb[p];
		sum[rs(p)]+=tagb[p]*suma[rs(p)];
	}
	taga[p]=tagb[p]=0;
}

void push_up(int p) {
	sum[p]=(sum[ls(p)]+sum[rs(p)]);
	suma[p]=(suma[ls(p)]+suma[rs(p)]);
	sumb[p]=(sumb[ls(p)]+sumb[rs(p)]);
}

void fu_point_a(int p,int l,int r,int x,int y) {
	if(l==r) {
		sum[p]=(sum[p]+1ull*(y-suma[p])*sumb[p]);
		suma[p]=y;
		return ;
	}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(x<=mid) fu_point_a(ls(p),l,mid,x,y);
	if(x>mid)  fu_point_a(rs(p),mid+1,r,x,y);
	push_up(p);
}

void fu_point_b(int p,int l,int r,int x,int y) {
	if(l==r) {
		sum[p]=(sum[p]+1ull*(y-sumb[p])*suma[p]);
		sumb[p]=y;
		return ;
	}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(x<=mid) fu_point_b(ls(p),l,mid,x,y);
	if(x>mid)  fu_point_b(rs(p),mid+1,r,x,y);
	push_up(p);
}

void add_qu_a(int p,int l,int r,int L,int R,int x) {
	if(L<=l&&r<=R) {
		sum[p]=1ull*sumb[p]*x+sum[p];
		suma[p]+=(r-l+1)*x;
		taga[p]+=x;
		return ;
	}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(L<=mid) add_qu_a(ls(p),l,mid,L,R,x);
	if(R>mid)  add_qu_a(rs(p),mid+1,r,L,R,x);
	push_up(p);
}

void add_qu_b(int p,int l,int r,int L,int R,int x) {
	if(L<=l&&r<=R) {
		sum[p]=1ull*suma[p]*x+sum[p];
		sumb[p]+=(r-l+1)*x;
		tagb[p]+=x;
		return ;
	}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(L<=mid) add_qu_b(ls(p),l,mid,L,R,x);
	if(R>mid)  add_qu_b(rs(p),mid+1,r,L,R,x);
	push_up(p);
}

ull query(int p,int l,int r,int L,int R) {
	if(L<=l&&r<=R) return sum[p];
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(L>mid) return query(rs(p),mid+1,r,L,R);
	if(R<=mid) return query(ls(p),l,mid,L,R);
	return query(ls(p),l,mid,L,R)+query(rs(p),mid+1,r,L,R);
}

void subtask() {
	for(int i=1; i<=n; i++) {
		while(top&&a[i]>a[st[top]]) top--;
		la[i]=st[top];
		st[++top]=i;
	}
	top=0;
	st[top]=0;
	for(int i=1; i<=n; i++) {
		while(top&&b[i]>b[st[top]]) top--;
		lb[i]=st[top];
		st[++top]=i;
	}
	
	while(q--) {
		memset(sum,0,sizeof(sum));
		memset(suma,0,sizeof(suma));
		memset(sumb,0,sizeof(sumb));
		memset(taga,0,sizeof(taga));
		memset(tagb,0,sizeof(tagb));
		int l,r;
		scanf("%d%d",&l,&r);
		ull ans=0;
		ans=a[l]*b[l];
		fu_point_a(1,1,n,l,a[l]);
		fu_point_b(1,1,n,l,b[l]);
		for(int i=l; i<=r-1; i++) {
			int k1=la[i+1];
			int k2=lb[i+1];
			if(la[i+1]==la[i]) 
				add_qu_a(1,1,n,la[i]+1,i,a[i+1]-a[i]);
			else 
				for(int j=la[i+1]+1; j<=i; j++)
					fu_point_a(1,1,n,j,a[i+1]);
			if(lb[i+1]==lb[i]) 
				add_qu_b(1,1,n,lb[i]+1,i,b[i+1]-b[i]);
			else 
				for(int j=lb[i+1]+1; j<=i; j++)
					fu_point_b(1,1,n,j,b[i+1]);
			fu_point_a(1,1,n,i+1,a[i+1]);
			fu_point_b(1,1,n,i+1,b[i+1]);
			ans=(ans+query(1,1,n,l,i+1));
		}
		printf("%llu\n",ans);
	}
}

void init() {
	for(int i=1; i<=n; i++)
		for(int j=i; j<=n; j++) {
			c[i][j]=max(c[i][j-1],a[j]);
			d[i][j]=max(d[i][j-1],b[j]);
			cnt[i][j]=1ull*c[i][j]*d[i][j];
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			cnt[i][j]=cnt[i][j]+cnt[i][j-1]+cnt[i-1][j]-cnt[i-1][j-1];
}

int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	//freopen("a.txt","w",stdout);
	scanf("%d%d",&T,&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);
	if(q<=5) subtask();
	else {
		init();
		for(int i=1; i<=q; i++) {
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%llu\n",cnt[r][r]-cnt[l-1][r]-cnt[r][l-1]+cnt[l-1][l-1]);
		}
	}
	return 0;
}