#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i) 
#define R(i, j, k) for(int i = (j); i >= (k); --i) 
#define ll long long 
#define vi vector < int > 
#define ull unsigned long long 
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 1 << 20, mod = 1e9 + 7;
int n, q;
int a[N], b[N];
ull f[N];

int ql[N], qr[N];
vi qry[N];

inline ull Inv(ull x) {
	ull ret = 1, cur = x;
	L(i, 1, 63) 
		if(cur >> i & 1) 
			ret += 1ull << i, cur += x << i;
	return ret;
}

ull ns[N], iv[N];

int stka[N], tpa;
int stkb[N], tpb;
ull X[N], Y[N];

ull s[N];

struct dt {
	ull w;
	int mut;
	dt(ull A = 0, int B = 0) {
		w = A, mut = B;
	}
	inline ull getv() {
		assert(mut >= 0);
		return w << mut;
	}
	void upd() {
		if(w) {
			while(!(w & 1)) 
				w >>= 1, mut += 1;
		}
	}
};
inline dt operator + (dt a, dt b) {
	if(a.w == 0) return b;
	if(b.w == 0) return a;
	a.upd(), b.upd();
	int mn = min(a.mut, b.mut);
	return dt((a.w << (a.mut - mn)) + (b.w << (b.mut - mn)), mn);
}
inline dt operator * (dt a, dt b) {
	return dt(a.w * b.w, a.mut + b.mut);
}

struct mat {
	dt f[2][2];
	mat () {
		f[0][0] = f[1][1] = dt(1, 0);
	}
};
mat operator * (mat a, mat b) {
	mat ret;
	ret.f[0][0] = ret.f[1][1] = dt(0, 0);
	L(i, 0, 1) L(j, i, 1) L(k, i, j) 
		ret.f[i][j] = ret.f[i][j] + a.f[i][k] * b.f[k][j];
	return ret;
} 

dt sum[N][2];
mat tag[N];

void upd(int x) {
	L(o, 0, 1) sum[x][o] = sum[x << 1][o] + sum[x << 1 | 1][o];
}

void build(int x, int L, int R) {
	if(L == R) return sum[x][0] = dt(1, 0), void();
	int mid = (L + R) >> 1;
	build(x << 1, L, mid);
	build(x << 1 | 1, mid + 1, R);
	upd(x);
}

void adv(int x, mat w) {
	if(x >= N) return ;
	sum[x][1] = sum[x][0] * w.f[0][1] + sum[x][1] * w.f[1][1];
	sum[x][0] = sum[x][0] * w.f[0][0];
	tag[x] = tag[x] * w;
}

void push(int x) {
	adv(x << 1, tag[x]), adv(x << 1 | 1, tag[x]), tag[x] = mat();
}

void Add(int x, int L, int R, int l, int r, mat c) {
	if(l <= L && R <= r) return adv(x, c);
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) Add(x << 1, L, mid, l, r, c);
	if(r > mid) Add(x << 1 | 1, mid + 1, R, l, r, c);
	upd(x);
}
ull query(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) 
		return sum[x][1].getv();
	push(x);
	ull sum = 0;
	int mid = (L + R) >> 1;
	if(l <= mid) sum += query(x << 1, L, mid, l, r);
	if(r > mid) sum += query(x << 1 | 1, mid + 1, R, l, r);
	return sum;
}

void dv(int l, int r, int x) {
	int cnt = 0;
	while(x % 2 == 0) ++cnt, x >>= 1;
	mat A;
	A.f[0][0] = dt(iv[x], -cnt), A.f[1][1] = dt(1, 0);
	Add(1, 1, n, l, r, A);
}
void mut(int l, int r, int x) {
	int cnt = 0;
	while(x % 2 == 0) ++cnt, x >>= 1;
	mat A;
	A.f[0][0] = dt(x, cnt), A.f[1][1] = dt(1, 0);
	Add(1, 1, n, l, r, A);
}

int main() {
//	return system("fc match.out match3.ans"), 0;
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int tiid;
	cin >> tiid >> n;
	L(i, 1, n) {
		cin >> a[i];
	}
	L(i, 1, n) {
		cin >> b[i];
	}
	for(int i = 1; i <= n; i += 2) 
		iv[i] = Inv(i);
	cin >> q;
	L(i, 1, q) {
		cin >> ql[i] >> qr[i];
		qry[qr[i]].emplace_back(i);
	}
	
	build(1, 1, n);
	L(i, 1, n) {
		while(tpa && a[stka[tpa]] < a[i]) 
			dv(stka[tpa - 1] + 1, stka[tpa], a[stka[tpa]]), --tpa;
		stka[++tpa] = i;
		mut(stka[tpa - 1] + 1, stka[tpa], a[stka[tpa]]);
		
		while(tpb && b[stkb[tpb]] < b[i]) 
			dv(stkb[tpb - 1] + 1, stkb[tpb], b[stkb[tpb]]), --tpb;
		stkb[++tpb] = i;
		mut(stkb[tpb - 1] + 1, stkb[tpb], b[stkb[tpb]]);
		
		mat A;
		A.f[0][0] = dt(1, 0), A.f[1][1] = dt(1, 0), A.f[0][1] = dt(1, 0);
		Add(1, 1, n, 1, i, A);
		
		for(auto u : qry[i]) {
			ns[u] = query(1, 1, n, ql[u], qr[u]);
		}
	}
	
	L(i, 1, q) {
		cout << ns[i] << '\n';
	}
	return 0;
}
