#include <bits/stdc++.h>
#define rep(i,j,k) for(int i = (j);i <= (k);i++)
#define per(i,j,k) for(int i = (j);i >= (k);i--)
#define eb emplace_back
#define pii pair <int,int>
#define mkp make_pair
#define ll long long
#define ull unsigned long long
using namespace std;

void chkmin(int &x,int y){
	if(x > y) x = y;
}

void chkmax(int &x,int y){
	if(x < y) x = y;
}

void chkmin(ll &x,ll y){
	if(x > y) x = y;
}

void chkmax(ll &x,ll y){
	if(x < y) x = y;
}
int TEST,n,q;
int a[250005],b[250005];

ull res[250005];
struct qry{
	int id,l,r;
};
vector <qry> Q[1000005];
vector <int> SP[1000005];
#define ls (rt * 2)
#define rs (rt * 2 + 1)

void spt(int rt,int l,int r,int L,int R,int id){
	if(l == L && r == R){
	//	printf("qry %d sp [%d,%d]\n",id,l,r);
		SP[rt].eb(id);
		return;
	}
	int mid = (l + r) >> 1;
	if(R <= mid){
		spt(ls,l,mid,L,R,id);	
	}else if(L > mid){
		spt(rs,mid+1,r,L,R,id);
	}else{
		spt(ls,l,mid,L,mid,id);
		spt(rs,mid+1,r,mid+1,R,id);
		Q[rt].eb((qry){id,L,R});
		//printf("qry %d [%d,%d] [%d,%d]\n",id,L,mid,mid+1,R);
	}
}
ull result[1000005];

int pre[250005][2],suf[250005][2];
int pos[250005][2];

int curL,curR;
struct SEGMENT{
	ull base[1000005],add[1000005],sum[1000005];
	ull c[250005];
	
	void pushup(int rt){
		sum[rt] = sum[ls] + sum[rs] + base[rt] * add[rt];
	}
	void upd(int rt,ull C){
		sum[rt] += base[rt] * C;
		add[rt] += C;
	}
	void build(int rt,int l,int r){
		add[rt] = sum[rt] = 0;
		if(l == r){
			base[rt] = c[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		base[rt] = base[ls] + base[rs];
	}
	void upload(int rt,int l,int r,int L,int R,ull C){
		if(L > R) return;
		if(l == L && r == R){
			upd(rt,C);
			return;
		}
		int mid = (l + r) >> 1;
		if(R <= mid){
			upload(ls,l,mid,L,R,C);
		}else if(L > mid){
			upload(rs,mid+1,r,L,R,C);
		}else{
			upload(ls,l,mid,L,mid,C);
			upload(rs,mid+1,r,mid+1,R,C);
		}
		pushup(rt);
	}
	void update(int L,int R,ull C){
		upload(1,curL,curR,L,R,C);
	}
	ull query(int rt,int l,int r,int L,int R,ull tag){
		if(l == L && r == R) return sum[rt] + tag * base[rt];
		int mid = (l + r) >> 1;
		tag += add[rt];
		if(R <= mid) return query(ls,l,mid,L,R,tag);
		else if(L > mid) return query(rs,mid+1,r,L,R,tag);
		else return query(ls,l,mid,L,mid,tag) + query(rs,mid+1,r,mid+1,R,tag);
	}
	ull qry(int L,int R){
		return query(1,curL,curR,L,R,0);
	}
}T[4];

vector <qry> P[250005];
int dbg;

void solve(int rt,int l,int r){
	if(l == r){
		result[rt] = (ull)a[l] * b[l];
		for(int id:SP[rt]) res[id] += result[rt];
		return;
	}
	int mid = (l + r) >> 1;
	solve(ls,l,mid);
	solve(rs,mid+1,r);
	//if(l == 1 && r == 4) dbg = 1;
	//else dbg = 0;
	result[rt] = result[ls] + result[rs];
	pre[mid + 1][0] = a[mid + 1];pre[mid + 1][1] = b[mid + 1];
	
	rep(i,mid + 2,r){
		pre[i][0] = max(pre[i - 1][0],a[i]);
		pre[i][1] = max(pre[i - 1][1],b[i]);
	}
	suf[mid][0] = a[mid];suf[mid][1] = b[mid];
	per(i,mid - 1,l){
		suf[i][0] = max(suf[i + 1][0],a[i]);
		suf[i][1] = max(suf[i + 1][1],b[i]);
	}

	int j = mid;
	rep(i,mid+1,r){
		while(j >= l && suf[j][0] < pre[i][0]) j--;
		pos[i][0] = j;
	}
	j = mid;
	rep(i,mid+1,r){
		while(j >= l && suf[j][1] < pre[i][1]) j--;
		pos[i][1] = j;
	}
	
	if(dbg){
		printf("suf:\n");
		rep(i,l,mid) printf("%d %d\n",suf[i][0],suf[i][1]);
		printf("pre:\n");
		rep(i,mid+1,r) printf("%d %d\n",pre[i][0],pre[i][1]);
		
		printf("pos[0]\n");
		rep(i,mid+1,r) printf("%d ",pos[i][0]);
		printf("pos[1]\n");
		rep(i,mid+1,r) printf("%d ",pos[i][1]);
	}
	
	rep(i,l,mid){
		T[0].c[i] = 1;
		T[1].c[i] = suf[i][0];
		T[2].c[i] = suf[i][1];
		T[3].c[i] = 1llu * suf[i][0] * suf[i][1];
	}
	T[0].build(1,l,mid);T[1].build(1,l,mid);T[2].build(1,l,mid);T[3].build(1,l,mid);
	curL = l;curR = mid;
	
	for(qry I:Q[rt]) P[I.r].eb(I);
	
	rep(i,mid+1,r){
		T[0].update(max(pos[i][0],pos[i][1]) + 1,mid,1llu * pre[i][0] * pre[i][1]);
		T[1].update(pos[i][1] + 1,pos[i][0],pre[i][1]);
		T[2].update(pos[i][0] + 1,pos[i][1],pre[i][0]);
		T[3].update(l,min(pos[i][0],pos[i][1]),1);
		for(qry I:P[i]){
			res[I.id] += T[0].qry(I.l,mid) + T[1].qry(I.l,mid) + T[2].qry(I.l,mid) + T[3].qry(I.l,mid);
		}
		P[i].clear();
	}
	result[rt] += T[0].qry(l,mid) + T[1].qry(l,mid) + T[2].qry(l,mid) + T[3].qry(l,mid);
	//printf("result [%d,%d] %llu\n",l,r,result[rt]);
	for(int id:SP[rt]) res[id] += result[rt];
}

void qread(int &x){
	x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
}

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	qread(TEST);qread(n);
	rep(i,1,n) qread(a[i]);
	rep(i,1,n) qread(b[i]);
	qread(q);
	int l,r;
	rep(i,1,q){
		qread(l);qread(r);
		spt(1,1,n,l,r,i);
	}
	cerr << clock() << endl;
	solve(1,1,n);
	rep(i,1,q) printf("%llu\n",res[i]);
	cerr << clock() << endl;
	return 0; 
}
