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

template <typename T>
inline void read(T &f) {
	f = 0; int fu = 0; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') fu = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		f = f * 10 + c - '0';
		c = getchar();
	}
	if (fu) f = -f;
}

typedef unsigned long long ull;

const int N = 5005;

vector < pair <int, int> > qry[N];
int a[N], b[N];
ull ans[N * 50], ret[N];
int T, n, m, q;

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.ans", "w", stdout);
	read(T); read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= n; i++) read(b[i]);
	read(q);
	for (int i = 1; i <= q; i++) {
		int l, r;
		read(l); read(r);
		qry[r].emplace_back(l, i);
	}
	for (int i = 1; i <= n; i++) {
		int ma = 0, mb = 0;
		ull sum = 0;
		for (int j = i; j >= 1; j--) {
			ma = max(ma, a[j]);
			mb = max(mb, b[j]);
			sum += 1ull * ma * mb;
			ret[j] += sum;
		}
		for (auto j : qry[i]) ans[j.second] = ret[j.first];
	}
	for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
	return 0;
}