#include <cstdio>
#include <algorithm>
#include <set>
#define ll long long
#define ull unsigned long long
using std::sort;
using std::set;

int read(){
	int x =0, f =0; char c =getchar();
	while(c < '0' || c > '9') (c == '-') ? f =1, c =getchar() : c =getchar();
	while(c >= '0' && c <= '9') x =(x<<1)+(x<<3)+(48^c), c =getchar();
	return (f) ? -x : x;
}

void write(const ull &x){
	if(x/10 != 0)
		write(x/10);
	putchar('0'+x%10);
}

const int MAXN =2.5e5+20, MAXT =(1<<19)+10;

int T, n;
struct qaq{
	int seq[MAXN];
	int rpos[MAXN]; // first > on right//
	
	int fa[MAXN], ls[MAXN], rs[MAXN], rt;
}a, b;

void initrpos(qaq &qwq){
	int stack[MAXN], top =0;
	for(int i =1; i <= n; ++i){
		while(top && qwq.seq[i] > stack[top-1])
			qwq.rpos[stack[top-1]] =i-1, --top;
		stack[top++] =qwq.seq[i];
	}
	while(top)
		qwq.rpos[stack[top-1]] =n, --top;
}

void build(qaq &qwq){
	int cur =1; qwq.rt =cur;
	for(int i =2; i <= n; ++i){
		while(qwq.seq[i] > qwq.seq[cur] && qwq.fa[cur] != 0)
			cur =qwq.fa[cur];
		if(qwq.seq[i] > qwq.seq[cur])
			qwq.ls[i] =cur, qwq.fa[cur] =i, cur =i;
		else{
			if(qwq.rs[cur] != 0)
				qwq.ls[i] =qwq.rs[cur], qwq.fa[qwq.rs[cur]] =i;
			qwq.rs[cur] =i, qwq.fa[i] =cur;
			cur =i;
		}
	}
	while(qwq.fa[cur] != 0)
		cur =qwq.fa[cur];
	qwq.rt =cur;
}

ull sum[MAXT], tagl[MAXT], tagr[MAXT];
int N;

ull gcd(ull mm, ull nn){
	if(mm == 0)
		return nn;
	else{
		while(mm ^=nn ^=mm ^=nn %=mm)
			;
		return nn;
	}
}

inline void pushup(const int &x){
	sum[x] =sum[x<<1]+sum[(x<<1)|1];
	const ull Gcd =gcd(sum[x<<1], sum[(x<<1)|1]);
	tagl[x] =sum[x<<1]/Gcd, tagr[x] =sum[(x<<1)|1]/Gcd;
}

inline void pushdown(const int &x){
	sum[x<<1] =sum[x]/(tagl[x]+tagr[x])*tagl[x];
	sum[(x<<1)|1] =sum[x]/(tagl[x]+tagr[x])*tagr[x];
}

void modify(const ull &val, const int &typ, const int &l, const int &r, const int &nl =1, const int &nr =N, const int &x =1){
	if(nl == nr){
		if(typ == 1)
			sum[x] *=val;
		else
			sum[x] /=val;
	}
	else{
		const int mid =(nl+nr)>>1;
		pushdown(x);
		if(r <= mid)
			modify(val, typ, l, r, nl, mid, x<<1);
		else if(l >= mid+1)
			modify(val, typ, l, r, mid+1, nr, (x<<1)|1);
		else
			modify(val, typ, l, mid, nl, mid, x<<1), modify(val, typ, mid+1, r, mid+1, nr, (x<<1)|1);
		pushup(x);
	}
}

ull query(const int &l, const int &r, const int &nl =1, const int &nr =N, const int &x =1){
	if(nl == nr)
		return sum[x];
	else{
		const int mid =(nl+nr)>>1;
		pushdown(x);
		ull ret =0;
		if(r <= mid)
			ret =query(l, r, nl, mid, x<<1);
		else if(l >= mid+1)
			ret =query(l, r, mid+1, nr, (x<<1)|1);
		else
			ret =query(l, mid, nl, mid, x<<1)+query(mid+1, r, mid+1, nr, (x<<1)|1);
		pushup(x);
		return ret;
	}
}

void buildseg(){
	N =1;
	while(N < n) N <<=1;
	for(int i =N; i <= 2*N-1; ++i)
		sum[i] =1, tagl[i] =1, tagr[i] =1;
	for(int i =N-1; i >= 1; --i)
		pushup(i);
}

struct qu{
	int l, r, qid;
	bool operator < (qu B) const{
		return r < B.r;
	}
}q[MAXN];

bool cmpp(const qu &A, const qu &B){
	return A.l < B.l;
}

void func(qaq &qwq, const int &i){
	if(qwq.rs[i] != 0){
		for(int u =qwq.rs[i]; u != 0; u =qwq.ls[u])
			modify(qwq.seq[u], 1, u, qwq.rpos[u]);
	}
}

ull ans[MAXN];

int main(){
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	T =read(), n =read();
	for(int i =1; i <= n; ++i)
		a.seq[i] =read();
	for(int i =1; i <= n; ++i)
		b.seq[i] =read();
	
	initrpos(a), initrpos(b);
	build(a), build(b);
	
	buildseg();
	
	for(int i =1; i <= n; i =a.rpos[i]+1)
		modify(a.seq[i], 1, i, a.rpos[i]);
	for(int i =1; i <= n; i =b.rpos[i]+1)
		modify(b.seq[i], 1, i, b.rpos[i]);
	
	int Q =read();
	for(int tt =0; tt < Q; ++tt){
		q[tt].l =read(), q[tt].r =read(), q[tt].qid =tt;
	}
	sort(q, q+Q, cmpp);
	set<qu> sett;
	for(int i =1, j =0; i <= n; ++i){
		while(j < Q && q[j].l == i)
			sett.insert(q[j]), ++j;
		while(!sett.empty() && sett.begin()->r < i)
			sett.erase(sett.begin());
		for(auto it =sett.begin(); it != sett.end(); ++it){
			ans[it->qid] +=query(i, it->r);
		}
		
		modify(a.seq[i], 2, i, a.rpos[i]);
		modify(b.seq[i], 2, i, b.rpos[i]);
		func(a, i);
		func(b, i);
	}
	for(int tt =0; tt < Q; ++tt)
		write(ans[tt]), putchar('\n');
}
