#include <bits/stdc++.h>

using namespace std;

namespace sub1 {
const int N = 3001;
typedef unsigned long long ULL;

int T, n, Q, l, r, lg2[N];
struct ST {
	int a[N], st[N][18];
	
	void read() {
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
			st[i][0] = i;
		}
		for (int i = 1; i < 18; ++i)
			for (int j = 1; j + (1 << i - 1) <= n; ++j)
				st[j][i] = a[st[j][i - 1]] > a[st[j + (1 << i - 1)][i - 1]] ?
						st[j][i - 1] : st[j + (1 << i - 1)][i - 1];
	}
	
	int qry(int l, int r) {
		int t = lg2[r - l + 1];
		return a[st[l][t]] > a[st[r - (1 << t) + 1][t]] ?
			st[l][t] : st[r - (1 << t) + 1][t];
	}
};
ST a, b;
ULL sum[N][N];

void main() {
	scanf("%d%d", &T, &n);
	lg2[1] = 0;
	for (int i = 2; i < N; ++i) lg2[i] = lg2[i / 2] + 1;
	a.read();
	b.read();
	for (int i = 1; i <= n; ++i)
		for (int j = i; j <= n; ++j)
			sum[i][j] = (ULL)a.a[a.qry(i, j)] * b.a[b.qry(i, j)];
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
	scanf("%d", &Q);
	while (Q--) {
		scanf("%d%d", &l, &r);
		printf("%llu\n", sum[r][r] - sum[r][l - 1] - sum[l - 1][r] + sum[l - 1][l - 1]);
	}
}
}

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	sub1::main();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
