#include <bits/stdc++.h>
#define ULL unsigned long long
using namespace std;
const int N = 250005, M = 1 << 19 | 9;
int n, m, i, j, k, x, y, a[N], b[N], u[M], s[N], t[N];
ULL ans[N];
struct XY {
	int x, y, i;
	bool operator<(const XY &A) const {
		return y < A.y;
	}
} d[N];
struct MR {
	ULL f[5][5];
} f[M], F, Y, Z;
struct DT {
	ULL g[5];
} g[M], z;
MR operator*(MR a, MR b) {
	MR c = Z;
	for (int i = 0; i < 5; i++) {
		for (int k = 0; k <= i; k++) {
			if (!a.f[i][k]) continue;
			for (int j = 0; j <= k; j++) {
				c.f[i][j] += a.f[i][k] * b.f[k][j];
			}
		}
	}
	return c;
}
DT operator*(MR a, DT b) {
	DT c = z;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j <= i; j++) {
			c.g[i] += a.f[i][j] * b.g[j];
		}
	}
	return c;
}
void build(int p, int l, int r) {
	g[p].g[0] = r - l + 1;
	if (l == r) return ;
	int m = l + r >> 1, lc = p << 1, rc = lc | 1;
	build(lc, l, m);
	build(rc, m + 1, r);
}
void xia(int p, int lc, int rc) {
	f[lc] = u[lc] ? f[p] * f[lc] : f[p];
	g[lc] = f[p] * g[lc];
	f[rc] = u[rc] ? f[p] * f[rc] : f[p];
	g[rc] = f[p] * g[rc];
	u[p] = 0;
	u[lc] = u[rc] = 1;
}
void gai(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		f[p] = u[p] ? F * f[p] : F, u[p] = 1;
		g[p] = F * g[p];
	} else {
		int m = l + r >> 1, lc = p << 1, rc = lc | 1;
		if (u[p]) xia(p, lc, rc);
		if (x <= m) gai(lc, l, m, x, y);
		if (y > m) gai(rc, m + 1, r, x, y);
		for (m = 0; m < 5; m++) {
			g[p].g[m] = g[lc].g[m] + g[rc].g[m];
		}
	}
}
ULL he(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) return g[p].g[4];
	int m = l + r >> 1, lc = p << 1, rc = lc | 1;
	ULL s = 0;
	if (u[p]) xia(p, lc, rc);
	if (x <= m) s += he(lc, l, m, x, y);
	if (y > m) s += he(rc, m + 1, r, x, y);
	return s;
}
int main() {
	scanf("%*d%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (i = 1; i <= n; i++) scanf("%d", &b[i]);
	scanf("%d", &m);
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &d[i].x, &d[i].y);
		d[i].i = i;
	}
	sort(d + 1, d + m + 1);
	for (i = 0; i < 5; i++) Y.f[i][i] = 1;
	build(1, 1, n);
	for (k = 1; k <= m; k++) {
		for (i = d[k - 1].y + 1; i <= d[k].y; i++) {
			while (x && a[i] > a[s[x]]) x--;
			F = Y;
			F.f[1][1] = F.f[3][3] = 0;
			F.f[1][0] = F.f[3][2] = a[i];
			gai(1, 1, n, s[x] + 1, i);
			while (y && b[i] > b[t[y]]) y--;
			F = Y;
			F.f[2][2] = F.f[3][3] = 0;
			gai(1, 1, n, t[y] + 1, i);
			F = Y;
			F.f[4][3] = 1;
			gai(1, 1, n, 1, s[++x] = t[++y] = i);
		}
		ans[d[k].i] = he(1, 1, n, d[k].x, d[k].y);
	}
	for (i = 1; i <= m; i++) printf("%llu\n", ans[i]);
}