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

template<typename T>
ostream& operator<<(ostream& ost, const vector<T>& a) {
	bool first = true;
	for (const T& x : a) {
		if (!first) ost << ",";
		ost << x, first = false;
	}
	return ost;
}

void debug_out() { cerr << "\n"; }

template<typename U, typename... T>
void debug_out(const U& x, const T&... args) {
	cerr << " " << x;
	debug_out(args...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) // debuger

struct tag {
	int l, r, ta, tb;
	unsigned long long xa, xb, val;
};

constexpr tag nulltag = {-1, -1, -1, -1, 0, 0, 0};

struct segtree {
	int p;
	vector<int> ls, rs, len;
	vector<unsigned long long> sa, sb, s, hs;
	vector<int> ht;
	vector<tag> t;

	void pushup(int u) {
		sa[u] = sa[ls[u]] + sa[rs[u]];
		sb[u] = sb[ls[u]] + sb[rs[u]];
		s[u] = s[ls[u]] + s[rs[u]];
		ht[u] = max(ht[ls[u]], ht[rs[u]]);
		hs[u] = hs[ls[u]] + (ht[u] - ht[ls[u]]) * s[ls[u]] + hs[rs[u]] + (ht[u] - ht[rs[u]]) * s[rs[u]];
	}

	void mod(int u, const tag& x) {
		// assert(x.l >= t[u].r);
		if (~t[u].ta and ~t[u].tb) t[u].val += (unsigned long long) (x.l - t[u].r) * t[u].ta * t[u].tb + t[u].ta * x.xa + t[u].tb * x.xb + x.val;
		else if (~t[u].ta) {
			t[u].xb += (unsigned long long) (x.l - t[u].r) * t[u].ta + x.xb;
			t[u].val += t[u].ta * x.xa + x.val;
		}
		else if (~t[u].tb) {
			t[u].xa += (unsigned long long) (x.l - t[u].r) * t[u].tb + x.xa;
			t[u].val += t[u].tb * x.xb + x.val;
		}
		else t[u] = x;
		if (~x.ta) t[u].ta = x.ta;
		if (~x.tb) t[u].tb = x.tb;
		t[u].r = x.r;
		hs[u] += (x.l - ht[u]) * s[u] + x.xa * sa[u] + x.xb * sb[u] + x.val * len[u];
		if (~x.ta and ~x.tb) s[u] = (unsigned long long) x.ta * x.tb * len[u];
		else if (~x.ta) s[u] = x.ta * sb[u];
		else if (~x.tb) s[u] = x.tb * sa[u];
		if (~x.ta) sa[u] = (unsigned long long) x.ta * len[u];
		if (~x.tb) sb[u] = (unsigned long long) x.tb * len[u];
		ht[u] = x.r;
		// debug(u, sa[u], sb[u], s[u], hs[u], ht[u]);
	}

	void pushdown(int u) {
		if (~t[u].ta or ~t[u].tb) {
			mod(ls[u], t[u]);
			mod(rs[u], t[u]);
			t[u] = nulltag;
		}
	}

	segtree(int n) : p(0), ls(n * 2), rs(n * 2), len(n * 2), sa(n * 2, 0), sb(n * 2, 0), s(n * 2, 0), hs(n * 2, 0), ht(n * 2, 0), t(n * 2, nulltag) {
		build(0, n);
	}

	int build(int l, int r) {
		int u = p++;
		len[u] = r - l;
		if (r - l == 1) return u;
		int mid = (l + r) / 2;
		ls[u] = build(l, mid);
		rs[u] = build(mid, r);
		return u;
	}

	void fixr(int x, int y, const tag& v, int u, int l, int r) {
		// if (u == 0) {
		// 	debug(x, y, v.l, v.r, v.ta, v.tb, v.xa, v.xb, v.val);
		// }
		if (y <= l or r <= x) return;
		if (x <= l and r <= y) return mod(u, v);
		int mid = (l + r) / 2;
		pushdown(u);
		fixr(x, y, v, ls[u], l, mid);
		fixr(x, y, v, rs[u], mid, r);
		pushup(u);
	}

	unsigned long long sumr(int x, int y, int t, int u, int l, int r) {
		if (y <= l or r <= x) return 0;
		if (x <= l and r <= y) return hs[u] + s[u] * (t - ht[u]);
		int mid = (l + r) / 2;
		pushdown(u);
		return sumr(x, y, t, ls[u], l, mid) + sumr(x, y, t, rs[u], mid, r);
	}
};

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int id, n;
	cin >> id >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	vector<int> b(n);
	for (int i = 0; i < n; ++i) cin >> b[i];
	int q;
	cin >> q;
	vector<unsigned long long> sum(q); 
	vector<vector<pair<int, int>>> ql(n + 1);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r, --l;
		ql[r].emplace_back(l, i);
	}
	vector<int> S = {-1}, T = {-1};
	segtree F(n);
	for (int r = 0; ; ++r) {
		for (const auto& [l, i] : ql[r]) sum[i] = F.sumr(l, r, r, 0, 0, n);
		if (r == n) break;
		while (~S.back() and a[r] > a[S.back()]) S.pop_back();
		while (~T.back() and b[r] > b[T.back()]) T.pop_back();
		F.fixr(S.back() + 1, r + 1, (tag) {r, r, a[r], -1, 0, 0, 0}, 0, 0, n);
		F.fixr(T.back() + 1, r + 1, (tag) {r, r, -1, b[r], 0, 0, 0}, 0, 0, n);
		S.push_back(r);
		T.push_back(r);
	}
	for (int i = 0; i < q; ++i) cout << sum[i] << '\n';
}