#ifndef TheCodeWasMadeByMooos
#define TheCodeWasMadeByMooos
#include<bits/stdc++.h>
#define endl '\n'
#define QAQ(n, m) for(ll i = n; i <= m; ++i)
#define QWQ(n, m) for(ll j = n; j <= m; ++j)
#define For(i, n, m) for(ll i = n; i <= m; ++i)
#define uQWQ(n, m) for(ll j = n; j >= m; --j)
#define uQAQ(n, m) for(ll i = n; i >= m; --i)
#define uFor(i, n, m) for(ll i = n; i >= m; --i)
#define FOpen(x) freopen (#x".in", "r", stdin), freopen (#x".out", "w", stdout)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll T, n, Q;
ull a[250010], b[250010], Ans, Pre[3001][3001];
struct SegTree {
	ull Tr[1000010], *a;
	SegTree (ull *A) : a (A) {}
	inline void Build (ll l = 1, ll r = n, ll Pos = 1) {
		if (l == r) return Tr[Pos] = a[l], void ();
		ll mid = (l + r) >> 1;
		Build (l, mid, Pos << 1), Build (mid + 1, r, Pos << 1 | 1);
		Tr[Pos] = max (Tr[Pos << 1], Tr[Pos << 1 | 1]);
	}
	ll Qx, Qy;
	inline ull _Query (ll l = 1, ll r = n, ll Pos = 1) {
		if (Qx <= l && r <= Qy) return Tr[Pos];
		if (Qy < l || r < Qx) return 0;
		ll mid = (l + r) >> 1;
		return max (_Query (l, mid, Pos << 1), _Query (mid + 1, r, Pos << 1 | 1));
	}
	inline ull Query (ll x, ll y) { Qx = x, Qy = y; return _Query (); }
}TrA (a), TrB (b);
template<typename T> inline void CkMax (T &A, T B) { A = max (A, B); }
int main () {
    FOpen (match), cin.tie (0), ios::sync_with_stdio (false);
    cin >> T >> n; QAQ (1, n) cin >> a[i]; QAQ (1, n) cin >> b[i]; cin >> Q;
	if (n <= 3000 && Q <= 3000) {
		TrA.Build (), TrB.Build ();
		For (p, 1, n) For (q, p, n) {
			// static ull MaxA, MaxB; MaxA = MaxB = 0;
			// For (t, p, q) CkMax (MaxA, a[t]), CkMax (MaxB, b[t]);
			// Pre[p][q] = MaxA * MaxB;
			Pre[p][q] = TrA.Query (p, q) * TrB.Query (p, q);
		}
		QAQ (1, n) QWQ (1, n) Pre[i][j] += Pre[i - 1][j] + Pre[i][j - 1] - Pre[i - 1][j - 1];
		while (Q--) {
			static ll l, r;
			cin >> l >> r;
			cout << Pre[r][r] - Pre[l - 1][r] - Pre[r][l - 1] + Pre[l - 1][l - 1] << endl;
		}
		return 0;
	}
}

#endif