#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 3005;
typedef unsigned long long ull;
int T, n, Q;
ull a[MAXN], b[MAXN], ma[MAXN][MAXN], mb[MAXN][MAXN], sum[MAXN][MAXN];


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("%ull", a+i);
	for (int i = 1; i <= n; i++) scanf("%ull", b+i);
	for (int i = 1; i <= n; i++) {
		ma[i][i]  = a[i];
		mb[i][i]  = b[i];
		for (int j = i+1; j <= n; j++) {
			ma[i][j] = max(ma[i][j-1], a[j]);
			mb[i][j] = max(mb[i][j-1], b[j]);
		}
	}
	for (int p = 1; p <= n; p++) {
		for (int r = p; r <= n; r++) {
			sum[p][r] = sum[p][r-1]+ma[p][r]*mb[p][r];
		}
	}
	scanf("%d", &Q);
	while (Q--) {
		int l, r;
		scanf("%d %d", &l, &r);
		ull ans = 0;
		for (int p = l; p <= r; p++) ans += sum[p][r];
		printf("%llu\n", ans);
	}
	return 0;
}