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

typedef unsigned long long ull;

const int N = 3e5 + 5;

int T, n, q, a[N], b[N];

ull ans[N];

struct query {
	int l, r, id;
};

struct atom {
	int a, b, len;
};

struct BIT {
	ull t[N];
	void modify(int x, ull y) {
		for (; x <= n; x += x & -x) t[x] += y;
	}
	ull query(int x) {
		ull res = 0;
		for (; x; x -= x & -x) res += t[x];
		return res;
	}
} t1, t2;

ull calc(vector<atom>& v1, vector<atom>& v2) {
	ull res = 0;
	
	int p = 0;
	for (auto x : v1) {
		while (p < (int)v2.size() && v2[p].a <= x.a) {
			t1.modify(v2[p].b, v2[p].len);
			t2.modify(v2[p].b, (ull)v2[p].len * v2[p].b);
			p++;
		}
		ull tmp = 0;
		tmp += (ull)t1.query(x.b) * x.b;
		tmp += (ull)(t2.query(n) - t2.query(x.b));
		res += (ull)x.a * x.len * tmp;
	}
	
	while (p) {
		--p;
		t1.modify(v2[p].b, -v2[p].len);
		t2.modify(v2[p].b, (ull)-v2[p].len * v2[p].b);
	}

	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	p = 0;
	
	for (auto x : v1) {
		while (p < (int)v2.size() && v2[p].a > x.a) {
			t1.modify(v2[p].b, (ull)v2[p].a * v2[p].len);
			t2.modify(v2[p].b, (ull)v2[p].a * v2[p].len * v2[p].b);
			p++;
		}
		ull tmp = 0;
		tmp += (ull)t1.query(x.b) * x.b;
		tmp += (ull)(t2.query(n) - t2.query(x.b));
		res += (ull)x.len * tmp;
	}

	while (p) {
		--p;
		t1.modify(v2[p].b, (ull)-v2[p].a * v2[p].len);
		t2.modify(v2[p].b, (ull)-v2[p].a * v2[p].len * v2[p].b);
	}
	
	return res;
}

void solve(int l, int r, vector<query>& Q) {
	if (l == r) {
		for (auto p : Q) {
			ans[p.id] += (ull)a[l] * b[r];
		}
		return ;
	}
	if (Q.empty()) {
		return ;
	}
	
	int mid = (l + r) >> 1;
	int ma = 0, mb = 0;
	vector<atom> ls, rs;
	for (int i = mid; i >= l; i--) {
		if (a[i] > ma || b[i] > mb) {
			ma = max(ma, a[i]);
			mb = max(mb, b[i]);
			ls.push_back((atom){ma, mb, 0});
		}
		++ls.back().len;
	} 
	ma = mb = 0;
	for (int i = mid + 1; i <= r; i++) {
		if (a[i] > ma || b[i] > mb) {
			ma = max(ma, a[i]);
			mb = max(mb, b[i]);
			rs.push_back((atom){ma, mb, 0});
		}
		++rs.back().len;
	}
	
	vector<query> lq, rq;
	for (auto p : Q) {
		if (p.l <= mid && p.r > mid) {
			int lcnt = mid - p.l + 1, rcnt = p.r - mid;
			
			assert(lcnt > 0 && rcnt > 0);
			vector<atom> v1, v2;
			
			for (auto x : ls) {
				int cnt = min(lcnt, x.len);
				v1.push_back((atom){x.a, x.b, cnt});
				lcnt -= cnt;
				if (!lcnt) break;
			}
			
			for (auto x : rs) {
				int cnt = min(rcnt, x.len);
				v2.push_back((atom){x.a, x.b, cnt});
				rcnt -= cnt;
				if (!rcnt) break;
			}
			
			ans[p.id] += calc(v1, v2);
		}
		if (p.l <= mid)
			lq.push_back((query){p.l, min(p.r, mid), p.id});
		
		if (p.r > mid)
			rq.push_back((query){max(p.l, mid + 1), p.r, p.id});
	}
	solve(l, mid, lq);
	solve(mid + 1, r, rq);
}

namespace brute {
	ull res[3005][3005];
	void main() {
		for (int i = 1; i <= n; i++) {
			int ma = 0, mb = 0;
			for (int j = i; j <= n; j++) {
				ma = max(ma, a[j]);
				mb = max(mb, b[j]);
				res[i][j] = res[i][j - 1] + (ull)ma * mb;
			}
		}
		for (int i = n; i; i--) {
			for (int j = i; j <= n; j++) {
				res[i][j] += res[i + 1][j];
			}
		}
		scanf("%d", &q);
		while (q--) {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%llu\n", res[l][r]);
		}
	}
};

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	
	scanf("%d%d", &T, &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
	if (n <= 3000) {
		brute::main();
		return 0;
	}
	vector<query> Q;
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		query x = (query){l, r, i};
		Q.push_back(x);
	}
	solve(1, n, Q);
	for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
	cerr << clock() << endl;
	return 0;
}