#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T &f) {
	f = 0; int fu = 0; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') fu = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		f = f * 10 + c - '0';
		c = getchar();
	}
	if (fu) f = -f;
}

typedef unsigned long long ull;

const int N = 250005;

struct mat { ull a[5][5]; } I;

mat operator * (const mat &a, const mat &b) {
	mat ans;
	for (int i = 0; i < 5; i++) for (int j = i; j < 5; j++) ans.a[i][j] = 0;
	for (int k = 0; k < 5; k++) {
		for (int i = 0; i <= k; i++) {
			if (!a.a[i][k]) continue;
			for (int j = k; j < 5; j++) {
				ans.a[i][j] += a.a[i][k] * b.a[k][j];
			}
		}
	}
	return ans;
}

mat operator + (const mat &a, const mat &b) {
	mat ans;
	for (int i = 0; i < 5; i++) {
		for (int j = i; j < 5; j++) {
			ans.a[i][j] = a.a[i][j] + b.a[i][j];
		}
	}
	return ans;
}

struct node_t { int l, r, tg; mat sum, tag; } p[N << 2];

vector < pair <int, int> > qry[N];
int a[N], b[N];
ull ans[N];
int T, n, q;

void update(int u) {
	p[u].sum = p[u << 1].sum + p[u << 1 | 1].sum;
}

void add_tag(int u, const mat &x) {
	p[u].sum = x * p[u].sum;
	if (!p[u].tg) {
		p[u].tag = x;
		p[u].tg = 1;
	} else {
		p[u].tag = x * p[u].tag;
	}
}

void pushdown(int u) {
	if (p[u].tg) {
		add_tag(u << 1, p[u].tag);
		add_tag(u << 1 | 1, p[u].tag);
		p[u].tg = 0;
	}
}

void build(int u, int l, int r) {
	p[u].l = l; p[u].r = r;
	if (l == r) {
		p[u].sum = I;
		return;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	update(u);
}

mat x;
void add(int u, int l, int r) {
	if (l <= p[u].l && p[u].r <= r) {
		add_tag(u, x);
		return;
	}
	pushdown(u);
	int mid = (p[u].l + p[u].r) >> 1;
	if (mid >= l) add(u << 1, l, r);
	if (mid + 1 <= r) add(u << 1 | 1, l, r);
	update(u);
}

ull query(int u, int l, int r) {
	if (l <= p[u].l && p[u].r <= r) return p[u].sum.a[0][4];
	pushdown(u);
	int mid = (p[u].l + p[u].r) >> 1; ull ans = 0;
	if (mid >= l) ans += query(u << 1, l, r);
	if (mid + 1 <= r) ans += query(u << 1 | 1, l, r);
	return ans;
}

int st1[N], st2[N], top1, top2;

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	for (int i = 0; i < 5; i++) I.a[i][i] = 1;
	read(T); read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= n; i++) read(b[i]);
	read(q);
	for (int i = 1; i <= q; i++) {
		int l, r;
		read(l); read(r);
		qry[r].emplace_back(l, i);
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		x = I;
		x.a[1][4] = 1ull * a[i] * b[i];
		x.a[2][4] = a[i];
		x.a[3][4] = b[i];
		add(1, i, i);
		while (top1 && a[st1[top1]] < a[i]) {
			x = I;
			x.a[1][3] = a[i] - a[st1[top1]];
			x.a[2][4] = a[i] - a[st1[top1]];
			add(1, st1[top1 - 1] + 1, st1[top1]);
			--top1;
		}
		while (top2 && b[st2[top2]] < b[i]) {
			x = I;
			x.a[1][2] = b[i] - b[st2[top2]];
			x.a[3][4] = b[i] - b[st2[top2]];
			add(1, st2[top2 - 1] + 1, st2[top2]);
			--top2;
		}
		st1[++top1] = i; st2[++top2] = i;
		x = I; x.a[0][1] = 1;
		add(1, 1, n);
		for (auto j : qry[i]) ans[j.second] = query(1, j.first, i);
	}
	for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
	return 0;
}