#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m, a[N], b[N], Ra[N], Rb[N], stk[N];
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	int T;
	cin >> T >> n;
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++i) scanf("%d", b + i);
	int tp = 0;
	stk[0] = n + 1;
	for (int i = n; i; --i) {
		while (tp && a[stk[tp]] < a[i]) --tp;
		Ra[i] = stk[tp];
		stk[++tp] = i;
	}
	for (int i = n; i; --i) {
		while (tp && b[stk[tp]] < b[i]) --tp;
		Rb[i] = stk[tp];
		stk[++tp] = i;
	}
//	for (int i = 1; i <= n; ++i) assert(Ra[i] && Rb[i]);
	cin >> m;
//	for (int i = 1; i <= n; ++i) printf("a[%d] = %d\n", i, a[i]);
//	for (int i = 1; i <= n; ++i) printf("b[%d] = %d\n", i, b[i]);
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		unsigned long long ans = 0;
//		for (int j = l; j <= r; ++j) {
//			int posa = j, posb = j, las = j, pos = j;
//			while (pos <= r) {
//				bool ff = 0;
//				int nxt;//cout << Rb[posb] << ' ' << Ra[posa] << endl;
//				if (Rb[posb] <= Ra[posa]) nxt = Rb[posb] - 1, ff = 0;
//				else nxt = Ra[posa] - 1, ff = 1;
//				nxt = min(nxt, r);printf("!! %d %d\n", pos, nxt);
//				ans += 1ull * (nxt - pos + 1) * a[posa] * b[posb];
//				if (ff) posa = nxt + 1;
//				else posb = nxt + 1;
//				pos = nxt + 1;
//			}printf("%d %llu\n", j, ans);
//		}//325775 319970
		ans = 0;	
		for (int j = l; j <= r; ++j) {
			int va = 0, vb = 0;
			for (int k = j; k <= r; ++k) {
				va = max(va, a[k]), vb = max(vb, b[k]);
				ans += 1ull * va * vb;
			}
		//	printf("%d %llu\n", j, ans);
		}
		printf("%llu\n", ans);
	}
}
/*0 2
2 1
1 2
1
1 2

*/
